On State-Synchronized Automata Systems

• Autorzy: Meduna A. , Kučera J.

Identyfikatory

DOI

10.4467/20838476SI.16.019.4360

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2015
• Tom: Vol. 24
• Strony: 221--237
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Meduna A.

• Formal Language Research Group, Department of Information Systems Faculty of Information Technology, Brno University of Technology Božetĕchova 2, 612 66 Brno, Czech Republic

autor

Kučera J.

• Formal Language Research Group, Department of Information Systems Faculty of Information Technology, Brno University of Technology Božetĕchova 2, 612 66 Brno, Czech Republic

Bibliografia

• [1] Čermák M., Meduna A., n-Accepting restricted pushdown automata systems. In: 13th International Conference on Automata and Formal Languages. Computer and Automation Research Institute, Hungarian Academy of Sciences, Nyíregyhá, 2011, pp. 168–183.
• [2] Chomsky N., Three models for the description of language. IRE Transactions on Information Theory, 1956, 2(3), pp. 113–124.
• [3] Csuhaj-Varjú E., Dassow J., Kelemen J., Páun Gh., Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London, 1994.
• [4] Csuhaj-Varjú E., Martín-Vide C., Mitrana V., Vaszil G., Parallel communicating pushdown automata systems. International Journal of Foundations of Computer Science, 2000, 11(4), pp. 631–650.
• [5] Harrison M.A., Introduction to Formal Language Theory. Addison-Wesley, Boston, 1978.
• [6] Kučera J., On state-synchronized automata systems. In: Drahansk M., Orság F. (eds.), Proceedings of the 19th Conference STUDENT EEICT 2013, Faculty of Information Technology Brno University of Technology, Brno, 2013, pp. 216–218.
• [7] Martín-Vide C., Mateescu A., Mitrana V., Parallel finite automata systems communicating by states. International Journal of Foundations of Computer Science, 2002, 13(5), pp. 733–749.
• [8] Meduna A., Automata and Languages: Theory and Applications. Springer, London, 2000.
• [9] Meduna A., Simultaneously one-turn two-pushdown automata. International Journal of Computer Mathematics, 2003(80), 2003, pp. 679–687.
• [10] Meduna A., Lukáš R., Multigenerative grammar systems. Schedae Informaticae, 2006, pp. 175–188.