ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA

DOI10.1142/S0129054112500062zbMath1279.68133MaRDI QIDQ2909225

Andreas Malcher, Martin Kutrib, Henning Bordihn

Publication date: 30 August 2012

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

zbMATH Keywords

formal languages; theory of computation; cooperating systems; automata systems

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

Cellular Automata: Descriptional Complexity and Decidability, Reversible parallel communicating finite automata systems, Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities, Asynchronous Parallel Communicating Systems of Pushdown Automata

Cites Work

• Unnamed Item
• Multiprocessor automata
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• On two-way multihead automata
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• On Communicating Finite-State Machines
• Church-Rosser Thue systems and formal languages
• k + 1 Heads Are Better than k
• Returning and non-returning parallel communicating finite automata are equivalent
• On Multi-Head Finite Automata
• Multi-tape and multi-head pushdown automata