Static Watson-Crick Linear Grammars and Its Computational Power

Authors

  • Aqilahfarhana Abdul Rahman Department of Mathematical Sciences, Universiti Teknologi Malaysia.
  • Fong Wan Heng Department of Mathematical Sciences, Universiti Teknologi Malaysia
  • Nor Haniza Sarmin Department of Mathematical Sciences, Universiti Teknologi Malaysia.
  • Sherzod Turaev Department of Computer Science, Faculty of Information and Communication Technology, International Islamic University Malaysia.
  • Nurul Liyana Mohamad Zulkufli Department of Computer Science, Faculty of Information and Communication Technology, International Islamic University Malaysia.

DOI:

https://doi.org/10.11113/matematika.v35.n3.1110

Abstract

DNA computing, or more generally, molecular computing, is a recent development on computations using biological molecules, instead of the traditional silicon-chips. 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 double-stranded 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. 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.

Downloads

Published

2019-12-01

How to Cite

Abdul Rahman, A., Heng, F. W., Sarmin, N. H., Turaev, S., & Mohamad Zulkufli, N. L. (2019). Static Watson-Crick Linear Grammars and Its Computational Power. MATEMATIKA: Malaysian Journal of Industrial and Applied Mathematics, 35(3). https://doi.org/10.11113/matematika.v35.n3.1110

Issue

Section

Articles