Static watson-crick linear grammars and its computational power

Abdul Rahman, Aqilahfarhana and Fong, Wan Heng and Sarmin, Nor Haniza and Sherzod Turaev, Sherzod and Mohamad Zulkufli, Nurul Liyana (2019) Static watson-crick linear grammars and its computational power. MATEMATIKA, 35 (3). pp. 283-296. E-ISSN 0127-9602

	PDF - Published Version Restricted to Repository staff only Download (171kB) | Request a copy
Preview	PDF (wos) - Supplemental Material Download (169kB) | Preview

Abstract

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.

Item Type:	Article (Journal)
Additional Information:	8371/79429
Uncontrolled Keywords:	Sticker system; computational power; Watson-Crick grammar; linear grammar.
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Computer software T Technology > T Technology (General)
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Engku Norulizati Engku Aziz
Date Deposited:	05 Mar 2020 14:18
Last Modified:	05 Mar 2020 14:18
URI:	http://irep.iium.edu.my/id/eprint/79429

Actions (login required)

View Item