Computational properties of Watson-Crick context-free grammars
Deoxyribonucleic acid, or popularly known as DNA, continues to inspire many theoretical computing models, such as sticker systems and Watson-Crick grammars. Sticker systems are the abstraction of ligation processes performed on DNA, while Watson-Crick grammars are models motivated from Watson-Crick...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English English |
| Published: |
The Institute of Electrical and Electronics Engineers, Inc.
2016
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/ http://irep.iium.edu.my/50833/1/50833_Computational_Properties_of_Watson-Crick1.pdf http://irep.iium.edu.my/50833/4/50833_Computational%20Properties_scopus.pdf |
| Summary: | Deoxyribonucleic acid, or popularly known as DNA, continues to inspire many theoretical computing models, such as sticker systems and Watson-Crick grammars. Sticker systems are the abstraction of ligation processes performed on DNA, while Watson-Crick grammars are models motivated from Watson-Crick finite automata and Chomsky grammars. Both of these theoretical models benefit from the Watson-Crick complementarity rule. In this paper, we establish the results on the relationship between Watson-Crick linear grammars, which is included in Watson-Crick context-free grammars, and sticker systems. We show that the family of arbitrary sticker languages, generated from arbitrary sticker systems, is included in the family of Watson-Crick linear languages, generated from Watson-Crick linear grammars. |
|---|