Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities
Authors:
- 1 December 2015
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 26 (08) , 1101-1126
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.Keywords
This publication has 8 references indexed in Scilit:
- Asynchronous Systems of Parallel Communicating Finite AutomataFundamenta Informaticae, 2015
- ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATAInternational Journal of Foundations of Computer Science, 2012
- UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATAInternational Journal of Foundations of Computer Science, 2011
- Returning and non-returning parallel communicating finite automata are equivalentRAIRO - Theoretical Informatics and Applications, 2007
- PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATESInternational Journal of Foundations of Computer Science, 2002
- On time computability of functions in one-way cellular automataActa Informatica, 1998
- Reversal-Bounded Multicounter Machines and Their Decision ProblemsJournal of the ACM, 1978
- On two-way multihead automataJournal of Computer and System Sciences, 1973