Detail publikace

Jumping Finite Automata

MEDUNA, A.; ZEMEK, P. Jumping Finite Automata. International Journal of Foundations of Computer Science, 2012, vol. 23, no. 7, p. 1555-1578. ISSN: 0129-0541.
Název česky
Skákající konečné automaty
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
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{BUT98563,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Jumping Finite Automata",
  journal="International Journal of Foundations of Computer Science",
  year="2012",
  volume="23",
  number="7",
  pages="1555--1578",
  doi="10.1142/S0129054112500244",
  issn="0129-0541",
  url="http://dx.doi.org/10.1142/S0129054112500244"
}
Nahoru