Publication Details

On State-Synchronized Automata Systems

KUČERA Jiří and MEDUNA Alexander. On State-Synchronized Automata Systems. Schedae Informaticae, vol. 2015, no. 24, 2016, pp. 221-237. ISSN 0860-0295. Available from: http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/
Czech title
O stavově synchronizovaných automatových systémech
Type
journal article
Language
english
Authors
URL
Keywords

state-synchronized automata systems, automata systems, pushdown automata, determinism, recursively enumerable languages

Abstract

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n.
In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

Published
2016
Pages
221-237
Journal
Schedae Informaticae, vol. 2015, no. 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"
}
Back to top