Detail publikace

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.
Název česky
Model skákajících 5'->3' Watson-Crickových konečných automatů
Typ
článek v časopise
Jazyk
anglicky
Autoři
Kocman Radim, Ing., Ph.D. (CVT)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
NAGY, B.
URL
Klíčová slova

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

Abstrakt

Skákající konečné automaty a 5'->3' Watson-Crickovy konečné automaty s detekcí setkání hlav jsou konečně-stavové modely výpočtu umožňující zpracovat vstupní větu nejen striktně zleva doprava. V tomto článku je prezentován nový model kombinující oba předchozí. Je studována síla nového modelu a provedeno porovnání s původními modely a také s klasickými třídami jazyků. Dále článek studuje změny síly v případě běžných omezení z oblasti Watson-Crickových konečných automatů jako například koncovost všech stavů aplikovaných na nový model. V závěru článek prezentuje ucelenou hierarchii souvisejících tříd jazyků.

Rok
2022
Strany
557–584
Časopis
Acta Informatica, roč. 59, č. 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"
}
Nahoru