DNA Computing: New Computing Paradigms

ISBN-13: 9783540641964 / Angielski / Twarda / 1998 / 400 str.

Gheorghe Paun;Grzegorz Rozenberg;Arto Salomaa

Opis

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."

Spis treści

Introduction: DNA Computing in a Nutshell.- I: Background and Motivation.- 1 DNA: Its Structure and Processing.- 2 Beginnings of Molecular Computing.- II: Mathematical Theory.- 3 Introduction to Formal Language Theory.- 4 Sticker Systems.- 5 Watson—Crick Automata.- 6 Insertion-Deletion Systems.- 7 Splicing Systems.- 8 Universality by Finite H Systems.- 9 Splicing Circular Strings.- 10 Distributed H Systems.- 11 Splicing Revisited.

Blurb

This is the first text and monograph about DNA computing, a molecular approach that might revolutionize our thinking and ideas about computing. Although it is too soon to predict whether computer hardware is likely to change from silicon to carbon and from microchips to DNA molecules, the theoretical premises have already been studied extensively. The book starts with an introduction to DNA-related matters, the basics of biochemistry and language and computation theory, and progresses to the advanced mathematical theory of DNA computing.

Apart from being well-known scientists, all three authors are known for their lucid writing. Many of their previous books have become classics in their field, and this book too is sure to follow their example.