Publication Details

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

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A.; NAGY, B. A Jumping 5'->3' Watson-Crick Finite Automata Model. Acta Informatica, 2022, vol. 59, no. 5, p. 557-584. ISSN: 0001-5903.
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. (CVT)
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
NAGY, B.
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
DOI
10.1007/s00236-021-00413-x
UT WoS
000745756500001
EID Scopus
2-s2.0-85123484658
BibTeX 
@article{BUT169467,
  author="KOCMAN, R. and KŘIVKA, Z. and MEDUNA, A. and NAGY, B.",
  title="A Jumping 5'->3' Watson-Crick Finite Automata Model",
  journal="Acta Informatica",
  year="2022",
  volume="59",
  number="5",
  pages="557--584",
  doi="10.1007/s00236-021-00413-x",
  issn="0001-5903",
  url="https://rdcu.be/cFzvd"
}
Back to top