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, 2018, s. 185-199. ISSN 0988-3754. Dostupné z: https://www.rairo-ita.org/articles/ita/abs/2018/02/ita180059/ita180059.html
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
Kocman Radim, Ing., Ph.D. (CVT FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
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
2018
Strany
185-199
Časopis
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 52, č. 2, ISSN 0988-3754
Vydavatel
EDP Sciences
DOI
10.1051/ita/2018013
UT WoS
000459294200007
EID Scopus
2-s2.0-85062218999
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 = 2018,
   ISSN = "0988-3754",
   doi = "10.1051/ita/2018013",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11313"
}
Nahoru