Static Watson-Crick Context-Free Grammars

Authors

  • Wan Heng Fong Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, UTM, Johor Bahru, Johor, Malaysia.
  • Aqilahfarhana Abdul Rahman Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, UTM, Johor Bahru, Johor, Malaysia.
  • Nor Haniza Sarmin Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, UTM, Johor Bahru, Johor, Malaysia.
  • Sherzod Turaev Faculty of Engineering and Natural Sciences, International University of Sarajevo, Hras-nicka cesta 15, 71210, Ilidza, Sarajevo, Bosnia and Herzegovina.

DOI:

https://doi.org/10.3991/ijoe.v15i10.10878

Abstract


Sticker systems and Watson-Crick automata are two modellings of DNA molecules in DNA computing. A sticker system is a computational model which is coded with single and double-stranded DNA molecules; while Watson-Crick automata is the automata counterpart of sticker system which represents the biological properties of DNA. Both of these models use the feature of Watson-Crick complementarity in DNA computing. Previously, the grammar counterpart of the Watson-Crick automata have been introduced, known as Watson-Crick grammars which are classified into three classes: Watson-Crick regular grammars, Watson-Crick linear grammars and Watson-Crick context-free grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick context-free grammar, which is a grammar counterpart of sticker systems that generates the double-stranded strings and uses rule as in context-free grammar, is introduced. The static Watson-Crick context-free grammar differs from a dynamic Watson-Crick context-free grammar in generating double-stranded strings, as well as for regular and linear grammars. The main result of the paper is to determine the generative powers of static Watson-Crick context-free grammars. Besides, the relationship of the families of languages generated by Chomsky grammars, sticker systems and Watson-Crick grammars are presented in terms of their hierarchy.

Downloads

Published

2019-06-27

How to Cite

Fong, W. H., Rahman, A. A., Sarmin, N. H., & Turaev, S. (2019). Static Watson-Crick Context-Free Grammars. International Journal of Online and Biomedical Engineering (iJOE), 15(10), pp. 65–76. https://doi.org/10.3991/ijoe.v15i10.10878

Issue

Vol. 15 No. 10 (2019)

Section

Papers

License

The submitting author warrants that the submission is original and that she/he is the author of the submission together with the named co-authors; to the extend the submission incorporates text passages, figures, data or other material from the work of others, the submitting author has obtained any necessary permission.
Articles in this journal are published under the Creative Commons Attribution Licence (CC-BY What does this mean?). This is to get more legal certainty about what readers can do with published articles, and thus a wider dissemination and archiving, which in turn makes publishing with this journal more valuable for you, the authors.
By submitting an article the author grants to this journal the non-exclusive right to publish it. The author retains the copyright and the publishing rights for his article without any restrictions.