Detail publikace

On Double-Jumping Finite Automata and Their Closure Properties

KOCMAN Radim, KŘIVKA Zbyněk a MEDUNA Alexander. On Double-Jumping Finite Automata and Their Closure Properties. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 52, č. 2, s. 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
angličtina
Autoři
URL
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
2019
Strany
185-199
Časopis
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 52, č. 2, ISSN 0988-3754
Vydavatel
EDP Sciences
DOI
BibTeX
@ARTICLE{FITPUB11313,
   author = "Radim Kocman and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "On Double-Jumping Finite Automata and Their Closure Properties",
   pages = "185--199",
   journal = "RAIRO - Theoretical Informatics and Applications - Informatique Th\'{e}orique et Applications",
   volume = 52,
   number = 2,
   year = 2019,
   ISSN = "0988-3754",
   doi = "10.1051/ita/2018013",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11313"
}
Nahoru