A Rice-style theorem for parallel automata

DOI10.1016/j.ic.2008.10.004zbMath1169.68025OpenAlexW2015892939MaRDI QIDQ1004287

Tirza Hirst

Publication date: 2 March 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.10.004

zbMATH Keywords

regular languagesRice's theoremPSPACE-hardstatechartsparallel automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Statecharts: a visual formalism for complex systems
• A calculus of communicating systems
• Complexity results for two-way and multi-pebble automata and their logics
• Modalities for model checking: Branching time logic strikes back
• Alternation and bounded concurrency are reverse equivalent.
• On the complexity of verifying concurrent transition systems
• Automata, logics, and infinite games. A guide to current research
• Relationships between nondeterministic and deterministic tape complexities
• Propositional dynamic logic of looping and converse is elementarily decidable
• Communicating sequential processes
• On the power of bounded concurrency I
• On the power of bounded concurrency II
• Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
• Decision problems forω-automata
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Classes of Recursively Enumerable Sets and Their Decision Problems

This page was built for publication: A Rice-style theorem for parallel automata