Detail publikace

On Double-Jumping Finite Automata and Their Closure Properties

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A. On Double-Jumping Finite Automata and Their Closure Properties. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2018, vol. 52, no. 2, p. 185-199. ISSN: 0988-3754.
Název česky
O dvojskokých konečných automatech a jejich uzávěrových vlastnostech
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)
URL
Klíčová slova

discontinuous and parallel tape reading, general jumping finite automata, even-length languages, left and right jumps

Abstrakt

Článek modifikuje skákající konečné automaty tak, že současně čtou a skákají na dvou místech pásky dle téhož pravidla. Pro současné skoky jsou uvažovány tři možnosti: (1) do leva, (2) doprava, (3) v různých směrech. Podle těchto možností článek zkoumá vzájemné relace tříd jazyků definovaných takto modifikovanými skákajícími automaty. Dále je zahrnuto porovnání i s regulárními, lineárními, bezkontextovými a kontextovými jazyky. Většina zkoumaných nových vztahů vede na vzájemnou neporovnatelnost. Dále je studována řada uzávěrových vlastností těchto nových tříd jazyků.

Rok
2018
Strany
185–199
Časopis
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, roč. 52, č. 2, ISSN 0988-3754
DOI
10.1051/ita/2018013
UT WoS
000459294200007
EID Scopus
2-s2.0-85062218999
BibTeX 
@article{BUT155797,
  author="Radim {Kocman} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="On Double-Jumping Finite Automata and Their Closure Properties",
  journal="RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS",
  year="2018",
  volume="52",
  number="2",
  pages="185--199",
  doi="10.1051/ita/2018013",
  issn="0988-3754",
  url="https://www.rairo-ita.org/articles/ita/abs/2018/02/ita180059/ita180059.html"
}
Nahoru