Detail publikace

On State-Synchronized Automata Systems

KUČERA, J.; MEDUNA, A. On State-Synchronized Automata Systems. Schedae Informaticae, 2016, vol. 2015, no. 24, p. 221-237. ISSN: 0860-0295.
Název česky
O stavově synchronizovaných automatových systémech
Typ
článek v časopise
Jazyk
anglicky
Autoři
Kučera Jiří, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
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
10.4467/20838476SI.16.019.4360
EID Scopus
2-s2.0-85020929200
BibTeX 
@article{BUT130905,
  author="Jiří {Kučera} and Alexandr {Meduna}",
  title="On State-Synchronized Automata Systems",
  journal="Schedae Informaticae",
  year="2016",
  volume="2015",
  number="24",
  pages="221--237",
  doi="10.4467/20838476SI.16.019.4360",
  issn="0860-0295",
  url="http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/"
}
Nahoru