Detail publikace

On State-Synchronized Automata Systems

KUČERA Jiří a MEDUNA Alexander. On State-Synchronized Automata Systems. Schedae Informaticae, roč. 2015, č. 24, 2016, s. 221-237. ISSN 0860-0295. Dostupné z: http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/
Název česky
O stavově synchronizovaných automatových systémech
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Klíčová slova

stavově synchronizované automatové systémy, automatové systémy, zásobníkové automaty, determinizmus

Abstrakt

V tomto článku zavádíme nový druh automatových systémů, zvané stavově synchronizované automatové systémy stupně n, jejichž komponentami je obecně n zásobníkových automatů. Výpočetní krok je v těchto systémech proveden pouze pokud konkatenací aktuálních stavů všech komponent získáme slovo patřící do řídícího jazyka systému. Hlavním přínosem článku je demonstrace schopnosti stavově synchronizovaných automatových systémů charakterizovat třídu rekurzivně vyčíslitelných jazyků, a to jak pro nedeterministické, tak i pro deterministické verze těchto systémů. Výpočetní sílu stavově synchronizovaných automatových systémů lze snížit omezením výpočetní síly jejich komponent.

Rok
2016
Strany
221-237
Časopis
Schedae Informaticae, roč. 2015, č. 24, ISSN 0860-0295
DOI
EID Scopus
BibTeX
@ARTICLE{FITPUB10754,
   author = "Ji\v{r}\'{i} Ku\v{c}era and Alexander Meduna",
   title = "On State-Synchronized Automata Systems",
   pages = "221--237",
   journal = "Schedae Informaticae",
   volume = 2015,
   number = 24,
   year = 2016,
   ISSN = "0860-0295",
   doi = "10.4467/20838476SI.16.019.4360",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10754"
}
Nahoru