Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Zemek Petr, Ing., Ph.D., UIFS (FIT)
Abstrakt

The present paper proposes a new investigation area in automata theory: jumping finite automata. These automata work like classical finite automata except that they read input words discontinuously; that is, after reading a symbol, they can jump over some symbols within the words and continue their computation from there. The paper establishes several results concerning jumping finite automata in terms of commonly investigated areas of automata theory, such as decidability and closure properties. Most importantly, it achieves several results that demonstrate differences between jumping finite automata and classical finite automata. In its conclusion, the paper formulates several open problems and suggests future investigation areas.

Klíčová slova

modified finite automata, discontinuous tape reading, basic properties, comparison with classical finite automata, perspectives

URL
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"
}
Projekty
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru