Static watson-crick linear grammars and its computational power
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Penerbit UTM Press.
2019
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/79429/ http://irep.iium.edu.my/79429/ http://irep.iium.edu.my/79429/4/79429_Static%20Watson-Crick%20Linear%20Grammars_article_new.pdf http://irep.iium.edu.my/79429/3/79429_Static%20Watson-Crick%20Linear%20Grammars_wos.pdf |
| Summary: | 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. |
|---|