Konferenzpaper

Jahr der Veröffentlichung: 2015

Seiten: 1101-1126

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 26

Heftnummer: 8

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054115400146

Konferenz: 14th International Conference on Automata and Formal Languages (AFL)

Verlag: World Scientific Publishing

Abstract: 
Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted, that is, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. The computational power and decidability problems are studied for returning systems, where components are set back to their initial states after having answered communication requests. It is proved that an infinite, strict hierarchy of language families exists, induced by the number of messages sent by their most economical acceptors. It is shown that at least one gap in this hierarchy exists. Some levels in the hierarchy are investigated in more detail.

Harvard-Zitierstil: Bordihn, H., Kutrib, M. and Malcher, A. (2015) Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities, International Journal of Foundations of Computer Science, 26(8), pp. 1101-1126. https://doi.org/10.1142/S0129054115400146

APA-Zitierstil: Bordihn, H., Kutrib, M., & Malcher, A. (2015). Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities. International Journal of Foundations of Computer Science. 26(8), 1101-1126. https://doi.org/10.1142/S0129054115400146