Undecidability and hierarchy results for parallel communicating finite automata

DOI10.1142/S0129054111008891MaRDI QIDQ2909096zbMATH OpenFDO

Authors Martin Kutrib, Andreas Malcher, Henning Bordihn

Publication date 29 August 2012

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

zbMATH Keywords

formal languagesdecidability questionscooperating systemsautomata systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Undecidability and hierarchy results for parallel communicating finite automata
• Some undecidable problems for parallel communicating finite automata systems
• Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
• On the computational capacity of parallel communicating finite automata
• On the Computational Capacity of Parallel Communicating Finite Automata
• scientific article; zbMATH DE number 1502112
• Asynchronous systems of parallel communicating finite automata
• The parallel complexity of finite-state automata problems
• scientific article; zbMATH DE number 1490952
• Undecidability results for deterministic communicating sequential processes

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• k + 1 Heads Are Better than k
• 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
• Some undecidable problems for parallel communicating finite automata systems

Cited in

(9)

• On the Computational Capacity of Parallel Communicating Finite Automata
• On the decidability of correctness problems for a communicating automata net
• A Rice-style theorem for parallel automata
• Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
• On the computational capacity of parallel communicating finite automata
• Undecidability and hierarchy results for parallel communicating finite automata
• Cellular automata: descriptional complexity and decidability
• Reversible parallel communicating finite automata systems
• Some undecidable problems for parallel communicating finite automata systems

This page was built for publication: Undecidability and hierarchy results for parallel communicating finite automata

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