Queen's University - Utility Bar

QSpace at Queen's University >
Graduate Theses, Dissertations and Projects >
Queen's Graduate Theses and 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

Files in This Item:

File Description SizeFormat
Sears_David_B_201012_MSc.pdf371 kBAdobe PDFView/Open
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 Graduate Theses and Dissertations
School of Computing Graduate Theses

Items in QSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


  DSpace Software Copyright © 2002-2008  The DSpace Foundation - TOP