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 languagestheory of computationcooperating systemsautomata systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

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

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