Static watson-crick linear grammars and its computational power

• Main Authors: Abdul Rahman, Aqilahfarhana, Fong, Wan Heng, Sarmin, Nor Haniza, Sherzod Turaev, Sherzod, Mohamad Zulkufli, Nurul Liyana
• Format: Article
• Language: English; English
• Published: Penerbit UTM Press. 2019
• Subjects: QA Mathematics; QA76 Computer software; T Technology (General)
• Online Access: http://irep.iium.edu.my/79429/4/79429_Static%20Watson-Crick%20Linear%20Grammars_article_new.pdf; http://irep.iium.edu.my/79429/3/79429_Static%20Watson-Crick%20Linear%20Grammars_wos.pdf; http://irep.iium.edu.my/79429/; https://matematika.utm.my/index.php/matematika/article/view/283-296/820
• Institution: Universiti Islam Antarabangsa Malaysia

DNA computing, or more generally, molecular computing, is a recent development on computations using biological molecules, instead of the traditional siliconchips. Some computational models which are based on different operations of DNA molecules have been developed by using the concept of formal language theory. The operations of DNA molecules inspire various types of formal language tools which include sticker systems, grammars and automata. Recently, the grammar counterparts of Watson-Crick automata known as Watson-Crick grammars which consist of regular, linear and context-free grammars, are defined as grammar models that generate doublestranded strings using the important feature of Watson-Crick complementarity rule. In this research, a new variant of static Watson-Crick linear grammar is introduced as an extension of static Watson-Crick regular grammar. A static Watson-Crick linear grammar is a grammar counterpart of sticker system that generates the double-stranded strings and uses rule as in linear grammar. There is a difference in generating double-stranded strings between a dynamic Watson-Crick linear grammar and a static Watson-Crick linear grammar. A dynamic Watson-Crick linear grammar produces each stranded string independently and only check for the Watson-Crick complementarity of a generated complete double-stranded string at the end; while the static Watson-Crick linear grammar generates both stranded strings dependently, i.e., checking for the WatsonCrick complementarity for each complete substring. The main result of the paper is to determine some computational properties of static Watson-Crick linear grammars. Next, the hierarchy between static Watson-Crick languages, Watson-Crick languages, Chomsky languages and families of languages generated by sticker systems are presented.