IIUM Repository

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.

[img] PDF - Published Version
Restricted to Repository staff only

Download (2MB) | Request a copy
[img]
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 View Item

Downloads

Downloads per month over past year