- Tytuł:
- On State-Synchronized Automata Systems
- Autorzy:
-
Meduna, Alexander
Kučera, Jiřĭ - Powiązania:
- https://bibliotekanauki.pl/articles/1373671.pdf
- Data publikacji:
- 2015
- Wydawca:
- Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
- Tematy:
-
pushdown automata
determinism
recursively enumerable languages
state-synchronized automata systems
automata systems - Opis:
- 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.
- Źródło:
-
Schedae Informaticae; 2015, 24; 221-237
0860-0295
2083-8476 - Pojawia się w:
- Schedae Informaticae
- Dostawca treści:
- Biblioteka Nauki
Artykuł