Detail publikace

Jumping Finite Automata

MEDUNA Alexander a ZEMEK Petr. Jumping Finite Automata. International Journal of Foundations of Computer Science, roč. 23, č. 7, 2012, s. 1555-1578. ISSN 0129-0541. Dostupné z: http://dx.doi.org/10.1142/S0129054112500244
Název česky
Skákající konečné automaty
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

modifikované konečné automaty, nespojité čtení pásky, základní vlastnosti, srovnání s klasickými konečnými automaty, perspektivy

Abstrakt

Článek zavádí novou oblast výzkumu v teorii automatů: skákající konečné automaty. Tyto automaty pracují jako klasické konečné automaty, ale čtou vstupní pásku nespojitě. To znamená, že po přečtení symbolu mohou skočit kamkoliv do vstupní pásky a pokračovat s výpočtem odtud. Článek studuje základní vlastnosti těchto automatů, jako je jejich síla, uzávěrové vlastnosti a rozhodnutelnost. Mezi nejdůležitější části článku patří demonstrace rozdílů mezi klasickými konečnými automaty a skákajícími konečnými automaty. V závěru článku je formulováno několik otevřených problémů.

Rok
2012
Strany
1555-1578
Časopis
International Journal of Foundations of Computer Science, roč. 23, č. 7, ISSN 0129-0541
DOI
10.1142/S0129054112500244
UT WoS
000314423000011
BibTeX 
@ARTICLE{FITPUB9795,
   author = "Alexander Meduna and Petr Zemek",
   title = "Jumping Finite Automata",
   pages = "1555--1578",
   journal = "International Journal of Foundations of Computer Science",
   volume = 23,
   number = 7,
   year = 2012,
   ISSN = "0129-0541",
   doi = "10.1142/S0129054112500244",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9795"
}
Nahoru