Abstract | ||
---|---|---|
We study binary word operations of the insertion, deletion and substitution type. Many of these operations can be generalized into a unified framework by introducing so-called trajectory condition. This generalization has been previously made for insertion and deletion operations. In this paper we naturally extend this approach also to substitution operations. We study closure properties and decision problems of substitutions on trajectories. The obtained results are then applied to model complex noisy channels and a cryptanalysis problem. Another application concerns the design of sets of DNA strands without undesired bonds. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1142/S0129054105003145 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
formal languages, trajectory, noisy channel, biocomputing | Combinatorics,Decision problem,Formal language,Computer science,Algorithm,Communication channel,Cryptanalysis,Theoretical computer science,Coding (social sciences),Trajectory,Binary number | Journal |
Volume | Issue | ISSN |
16 | 3 | 0129-0541 |
Citations | PageRank | References |
2 | 0.39 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lila Kari | 1 | 1123 | 124.45 |
Stavros Konstantinidis | 2 | 283 | 31.10 |
Petr Sosík | 3 | 479 | 68.66 |