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. / Thesis (Master, Computing) -- Queen's University, 2010-12-06 18:29:23.584

We deal with text processing, pattern matching and syntax analysis every day, and new areas emerging. We can consider programming languages, communication protocols or a simple text as well-know examples. Therefore, we need new effective methods which fit into these areas. In this work, we explore the topics of parallel grammars, E0L-systems and multigenerative grammar systems. The goal is to improve the Cocke-Younger-Kasami algorithm and present a stronger algorithm of analysis.