Publication Details

A Jumping 5'->3' Watson-Crick Finite Automata Model

KOCMAN Radim, KŘIVKA Zbyněk, MEDUNA Alexander and NAGY Benedek. A Jumping 5'->3' Watson-Crick Finite Automata Model. Acta Informatica, vol. 59, no. 5, 2022, pp. 557-584. ISSN 0001-5903. Available from: https://rdcu.be/cFzvd
Czech title
Model skákajících 5'->3' Watson-Crickových konečných automatů
Type
journal article
Language
english
Authors
Kocman Radim, Ing., Ph.D. (CC FIT BUT)
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Nagy Benedek, Dr. (EMU)
URL
Keywords

jumping automata, Watson-Crick automata, DNA computer, 2-head automata, discontinuous information processing, formal languages

Abstract

Jumping finite automata and sensing 5'->3' Watson-Crick finite automata are finite-state models of computation which allow to process the input word not only in the strictly left-to-right manner.
In this paper a new combined model of them is presented.
The accepting power of the new model is studied and compared with the original models and also other well-known language families. Furthermore, the paper investigates changes in the accepting power when commonly studied restrictions from Watson-Crick finite automata, e.g., all states are final, are applied to this combined model. In the end, the paper presents a comprehensive hierarchy of all related language families.

Published
2022
Pages
557-584
Journal
Acta Informatica, vol. 59, no. 5, ISSN 0001-5903
Publisher
Springer Verlag
DOI
10.1007/s00236-021-00413-x
UT WoS
000745756500001
EID Scopus
2-s2.0-85123484658
BibTeX 
@ARTICLE{FITPUB12083,
   author = "Radim Kocman and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna and Benedek Nagy",
   title = "A Jumping 5'->3' Watson-Crick Finite Automata Model",
   pages = "557--584",
   journal = "Acta Informatica",
   volume = 59,
   number = 5,
   year = 2022,
   ISSN = "0001-5903",
   doi = "10.1007/s00236-021-00413-x",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12083"
}
Back to top