Nagy, Benedek (2023) On language classes accepted by stateless 5′ → 3′ Watson-Crick finite automata Annales Mathematicae et Informaticae. 58. pp. 110-120. ISSN 1787-6117 (Online)
![[thumbnail of AMI_58_from110to120.pdf]](http://publikacio.uni-eszterhazy.hu/style/images/fileicons/text.png) |
pdf
AMI_58_from110to120.pdf Download (511kB) [error in script] |
Absztrakt (kivonat)
Watson-Crick automata are belonging to the natural computing paradigm as these finite automata are working on strings representing DNA molecules. Watson-Crick automata have two reading heads, and in the 5 ′ → 3 ′ models these two heads start from the two extremes of the input. This is well motivated by the fact that DNA strands have 5 ′ and 3 ′ ends based on the fact which carbon atoms of the sugar group is used in the covalent bonds to continue the strand. However, in the two stranded DNA, the directions of the strands are opposite, so that, if an enzyme would read the strand it may read each strand in its 5 ′ to 3 ′ direction, which means physically opposite directions starting from the two extremes of the molecule. On the other hand, enzymes may not have inner states, thus those Watson-Crick automata which are stateless (i.e. have exactly one state) are more realistic from this point of view. In this paper these stateless 5 ′ → 3 ′ Watson-Crick automata are studied and some properties of the language classes accepted by their variants are proven. We show hierarchy results, and also a “pumping”, i.e., iteration result for these languages that can be used to prove that some languages may not be in the class accepted by the class of stateless 5 ′ → 3 ′ Watson-Crick automata.
| Mű típusa: | Folyóiratcikk - Journal article |
|---|---|
| Szerző: | Szerző neve Email MTMT azonosító ORCID azonosító Közreműködés Nagy, Benedek NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző |
| Kapcsolódó URL-ek: | |
| Kulcsszavak: | Bio-computing, stateless finite automata, linear languages |
| Folyóirat alcíme: | Selected papers of the 12th International Conference on Applied Informatics |
| Nyelv: | angol |
| Kötetszám: | 58. |
| DOI azonosító: | 10.33039/ami.2023.08.004 |
| ISSN: | 1787-6117 (Online) |
| Felhasználó: | Tibor Gál |
| Dátum: | 21 Aug 2023 06:40 |
| Utolsó módosítás: | 10 Nov 2023 14:03 |
| URI: | http://publikacio.uni-eszterhazy.hu/id/eprint/7706 |
 |
Tétel nézet |
