On the Computational Capacity of Parallel Communicating Finite Automata

DOI10.1007/978-3-540-85780-8_11MaRDI QIDQ3533006zbMATHOpenAlexFDO

Authors Martin Kutrib, Andreas Malcher, Henning Bordihn

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_11

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the computational capacity of parallel communicating finite automata
• scientific article; zbMATH DE number 1502112
• The parallel complexity of finite-state automata problems
• Undecidability and hierarchy results for parallel communicating finite automata
• Undecidability and hierarchy results for parallel communicating finite automata
• Measuring communication in parallel communicating finite automata
• On Parallel Implementations of Deterministic Finite Automata
• scientific article; zbMATH DE number 1419219
• Some undecidable problems for parallel communicating finite automata systems
• scientific article; zbMATH DE number 1490952

Cites work

• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 745858 (Why is no real title available?)
• k + 1 Heads Are Better than k
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Church-Rosser Thue systems and formal languages
• Multi-tape and multi-head pushdown automata
• Multiprocessor automata
• On Communicating Finite-State Machines
• On Multi-Head Finite Automata
• On two-way multihead automata
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• Returning and non-returning parallel communicating finite automata are equivalent
• The Boolean Closure of Growing Context-Sensitive Languages

Cited in

(15)

• Measuring communication in parallel communicating finite automata
• On Parallel Implementations of Deterministic Finite Automata
• scientific article; zbMATH DE number 2106350 (Why is no real title available?)
• Reversible parallel communicating finite automata systems
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• scientific article; zbMATH DE number 1531819 (Why is no real title available?)
• Returning and non-returning parallel communicating finite automata are equivalent
• Some undecidable problems for parallel communicating finite automata systems
• Complexity of multi-head finite automata: origins and directions
• scientific article; zbMATH DE number 1795910 (Why is no real title available?)
• On the computational capacity of parallel communicating finite automata
• Undecidability and hierarchy results for parallel communicating finite automata
• Undecidability and hierarchy results for parallel communicating finite automata
• Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
• Systems of parallel communicating restarting automata

This page was built for publication: On the Computational Capacity of Parallel Communicating Finite Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533006)