Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities

DOI10.1142/S0129054115400146zbMath1338.68141MaRDI QIDQ2800414

Martin Kutrib, Andreas Malcher, Henning Bordihn

Publication date: 15 April 2016

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

distributed computationcomplexity induced by communicationsystems of finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (2)

Cellular Automata: Descriptional Complexity and Decidability ⋮ Reversible parallel communicating finite automata systems

Cites Work

• On time computability of functions in one-way cellular automata
• On two-way multihead automata
• UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA
• ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Returning and non-returning parallel communicating finite automata are equivalent

This page was built for publication: Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities