Computational properties of Watson-Crick context-free grammars

Mohamad Zulkufli, Nurul Liyana and Turaev, Sherzod and Mohd Tamrin, Mohd Izzuddin and Az Eddine, Messikh and Alshaikhli, Imad Fakhri Taha (2016) Computational properties of Watson-Crick context-free grammars. In: 2015 4th International Conference on Advanced Computer Science Applications and Technologies (ACSAT 2015), 8th-10th Dec. 2015, Kuala Lumpur.

	PDF - Published Version Restricted to Repository staff only Download (2MB) | Request a copy
Preview	PDF (scopus) Download (252kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Plenary Papers)
Additional Information:	6846/50833
Uncontrolled Keywords:	Watson-Crick grammars; Watson-Crick automata; sticker systems; formal languages; formal grammars
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
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 Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology > Department of Information System
Depositing User:	Mohd Izzuddin Mohd Tamrin
Date Deposited:	01 Jul 2016 15:25
Last Modified:	21 Apr 2017 15:34
URI:	http://irep.iium.edu.my/id/eprint/50833

Actions (login required)

View Item