Computational properties of Watson-Crick context-free grammars

• Main Authors: Mohamad Zulkufli, Nurul Liyana, Turaev, Sherzod, Mohd Tamrin, Mohd Izzuddin, Az Eddine, Messikh, Alshaikhli, Imad Fakhri Taha
• Format: Conference or Workshop Item
• Language: English; English
• Published: The Institute of Electrical and Electronics Engineers, Inc. 2016
• Subjects: QA75 Electronic computers. Computer science
• Online Access: 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; http://irep.iium.edu.my/50833/; http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7478741&filter%3DAND%28p_IS_Number%3A7478698%29%26pageNumber%3D2
• Institution: Universiti Islam Antarabangsa Malaysia

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.