Přístupnostní navigace
E-application
Search Search Close
Publication detail
KUČERA, J. MEDUNA, A.
Original Title
On State-Synchronized Automata Systems
Type
journal article in Scopus
Language
English
Original 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.
Keywords
state-synchronized automata systems, automata systems, pushdown automata, determinism, recursively enumerable languages
Authors
KUČERA, J.; MEDUNA, A.
Released
11. 5. 2016
ISBN
0860-0295
Periodical
Schedae Informaticae
Year of study
2015
Number
24
State
Republic of Poland
Pages from
221
Pages to
237
Pages count
17
URL
http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/
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/" }