|
QSpace at Queen's University >
Theses, Dissertations & Graduate Projects >
Queen's Theses & Dissertations >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1974/6224
|
| Title: | The Computational Power of Extended Watson-Crick L Systems |
| Authors: | Sears, David |
|
|
| Keywords: | Formal Languages
Lindenmayer system
DNA Computing
Watson-Crick complementarity
recursively enumerable language
E0L system |
| Issue Date: | 2010 |
| Series/Report no.: | Canadian theses |
| Abstract: | Lindenmayer (L) systems form a class of interesting computational formalisms due to their parallel nature, the various circumstances under which they operate, the restrictions imposed on language acceptance, and other attributes. These systems have been extensively studied in the
Formal Languages literature. In the past decade a new type of Lindenmayer system had been proposed: Watson-Crick Lindenmayer Systems. These systems are essentially a marriage between Developmental systems and DNA Computing. At their heart they are Lindenmayer systems augmented with a complementary relation amongst elements in the system just as the base pairs of DNA strands can be complementary with respect to one another. When conditions and a mechanism for 'switching' the state of a computation to it's complementary version are provided then these systems can become surprisingly more powerful than the L systems which form their backbone. This dissertation explores the computational power of new variants of Watson-Crick L systems. It is found that many of these systems are Computationally-Complete. These investigations differ from prior ones in that the systems under consideration have extended alphabets and usually Regular Triggers for complementation are considered as opposed to Context-Free Triggers investigated in previous works. |
| Description: | Thesis (Master, Computing) -- Queen's University, 2010-12-06 18:29:23.584 |
| URI: | http://hdl.handle.net/1974/6224 |
| Appears in Collections: | Queen's Theses & Dissertations
Computing Graduate Theses
|
Items in QSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
