Conference paper

Publication year: 2015

Pages: 1101-1126

Journal: International Journal of Foundations of Computer Science

Volume number: 26

Issue number: 8

ISSN: 0129-0541

eISSN: 1793-6373

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

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

Publisher: 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 Citation style: 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 Citation style: 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