DNA Computing: New Computing Paradigms

Front Cover
Springer Science & Business Media, Jan 1, 1998 - Computers - 402 pages
0 Reviews
The 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
Bibliography
383
Index
399
Copyright

Common terms and phrases

References to this book

All Book Search results »

About the author (1998)

Paun from the Romanian Academy

Junghei Chen received his Ph.D. in Chemistry from NYU, under the supervision of Ned Seeman. He has since worked at Berkeley and is now Associate Professor in the Department of Chemistry and Biochemistry at the University of Delaware. He has edited a Springer book: LNCS 2943, Int. Workshop on DNA Based Computers, DNA 9 (2003). He has authored dozens of papers in key journals areas of chemistry, biochemistry, physics, computing and nanoscience

Natascha Jonoska received her Ph.D. in Mathematical Science from SUNY Binghamton and is currently Associate Professor in the Mathematics Dept. at the University of South Florida. She has coedited a number of Springer books: LNCS 2723, Genetic and Evolutionary Computation Conf., GECCO 2003; LNCS 2950, Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (2004). Natasha has also contributed chapters in various Natural Computing books, and many journal and LNCS articles. Her journal publications cover her interests in both theoretical computer science and natural computing.

Grzegorz Rozenberg is the editor of the Springer Natural Computing series; is one of the series editors of the Springer EATCS Texts in Theoretical Computer Science series; was until this year the editor of the Springer journal Natural Computing; is the editor of the Elsevier Theoretical Computer Science journal Track C (Natural Computing). He has also edited or authored dozens of Springer books over the last 30 years. He has authored hundreds of publications in theoretical computer science and natural computing, and has been involved in the organization of dozens of conferences in both communities. He has authored and editeddozens of LNCS volumes and monographs, across a range of theoretical computer science fields and also in the area of natural computing. He has also recently edited some relevant Natural Computing series and EATCS series books, such as: Modelling in Molecular Biology (2004); Computation in Living Cells (2004); DNA Computing -- New Computing Paradigms (Reprint 2005). He also coedited LNCS 2950, Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (2004).

Salomaa from the University of Turku