## DNA Computing: New Computing ParadigmsThe authors are much indebted to many friends and collaborators whose con tributions to automata and language theory approach to DNA computing can be recognized in the present book. The bibliography specifies their names and we shall not repeat them here. Some of them have also read previous versions of various chapters, suggesting modifications which have improved the readability of the text. Many thanks are due in this respect to Tom Head, Hendrik Jan Hoogeboom, Vincenzo Manca, Alexandru Mateescu, Victor Mi trana, Andrei Paun, and Nike van Vugt. In particular, we are grateful to our biologist friends Hans Kusters and Paul Savelkoul for many illuminating discussions. Anu Heinimiiki drew the pictures in the Introduction. The ex pert assistance and timely cooperation of Springer-Verlag, notably Dr. Hans Wossner, is gratefully acknowledged. Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa Leiden, July 1998 Contents Introduction: DNA Computing in a Nutshell 1 Part I: Background and Motivation 7 1 DNA: Its Structure and Processing 9 1. 1 The Structure of DNA . . . . . 9 1. 2 Operations on DNA Molecules 19 1. 3 Reading out the Sequence 36 1. 4 Bibliographical Notes . . . . . . 40 2 Beginnings of Molecular Computing 43 2. 1 Adleman's Experiment. . . . . . . . . . . . . . . . . . . . . . 43 2. 2 Can We Solve the Satisfiability Problem and Break the DES Code? . . . . . . . . . . . . . . . . . . . . . 50 2. 3 Paradigm of Computing - Some Rethinking 65 2. 4 DNA Computing: Hopes and Warnings 71 Part II: Mathematical Theory 75 3 Introduction to Formal Language Theory 77 3. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

DNA Its Structure and Processing | 9 |

12 Operations on DNA Molecules | 19 |

13 Reading out the Sequence | 36 |

14 Bibliographical Notes | 40 |

Beginnings of Molecular Computing | 43 |

22 Can We Solve the Satisfiability Problem and Break the DES Code? | 50 |

23 Paradigm of Computing Some Rethinking | 65 |

Hopes and Warnings | 71 |

64 Using Only Insertion | 206 |

65 Bibliographical Notes | 215 |

Splicing Systems | 217 |

72 NonIterated Splicing as an Operation with Languages | 221 |

73 Iterated Splicing as an Operation with Languages | 229 |

74 Extended H Systems Generative Power | 241 |

75 Simple H Systems | 249 |

76 Bibliographical Notes | 255 |

Mathematical Theory | 75 |

Introduction to Formal Language Theory | 77 |

32 Characterizations of Recursively Enumerable Languages | 98 |

33 Universal Turing Machines and Type0 Grammars | 107 |

34 Bibliographical Notes | 116 |

Sticker Systems | 117 |

42 Sticker Systems Classifications | 122 |

43 The Generative Capacity of Sticker Systems | 127 |

44 Representations of Regular and Linear Languages | 136 |

45 Characterizations of Recursively Enumerable Languages | 139 |

46 More About Regular Sticker Systems | 142 |

47 Bibliographical Notes | 149 |

WatsonCrick Automata | 151 |

51 WatsonCrick Finite Automata | 152 |

52 Relationships Between the WK Families | 155 |

53 Characterizations of Recursively Enumerable Languages | 162 |

54 WatsonCrick Finite Transducers | 166 |

55 Further Variants of WatsonCrick Finite Automata | 168 |

56 WatsonCrick Automata with a WatsonCrick Memory | 174 |

57 Universality Results for WatsonCrick Automata | 180 |

58 Bibliographical Notes | 186 |

InsertionDeletion Systems | 187 |

62 Characterizations of Recursively Enumerable Languages | 189 |

63 One Symbol InsertionDeletion Systems | 200 |

Universality by Finite H Systems | 257 |

82 Permitting and Forbidding Contexts | 259 |

83 Target Languages | 271 |

84 Programmed and Evolving Systems | 276 |

85 H Systems Based on Double Splicing | 288 |

86 Multisets | 292 |

87 Universality Results | 300 |

88 Bibliographical Notes | 305 |

Splicing Circular Strings | 307 |

92 One Further Variant and its Power | 311 |

93 Bibliographical Notes | 320 |

Distributed H Systems | 321 |

102 Communicating Distributed H Systems | 331 |

103 TwoLevel Distributed H Systems | 341 |

104 TimeVarying Distributed H Systems | 348 |

105 Summary of Computationally Complete H Systems | 354 |

106 Bibliographical Notes | 355 |

Splicing Revisited | 357 |

112 Replication Systems | 365 |

113 Bibliographical Notes | 380 |

383 | |

399 | |

### Common terms and phrases

arbitrary automata axioms characterize Chomsky Chomsky hierarchy Church-Turing Thesis circular string component consider construct contains context-free languages Corollary defined denote derivation in G deterministic distributed H systems DNA computing DNA molecules encoding extended H system family of languages finite set forbidding contexts grammar G grammar systems H scheme Hamiltonian path hand end hence inclusion input insdel system insertion Kuroda normal form Lemma memory complexes morphisms multiset nonterminal nucleotides occurrence oligonucleotides pairs parsing permitting contexts prefix produced proof of Lemma recursively enumerable languages regular language replaced replication system restriction enzymes result rewriting rule of type rules in group Sect set of splicing simulate single stranded splicing operation splicing rules step sticker system sticky ends substrands substring symbols tape terminal string test tube Turing machine type-0 grammar upper strand variants Watson-Crick automaton Watson-Crick finite automaton weak coding WKP(V