A Rice-style theorem for parallel automata
From MaRDI portal
Publication:1004287
DOI10.1016/J.IC.2008.10.004zbMATH Open1169.68025OpenAlexW2015892939MaRDI QIDQ1004287FDOQ1004287
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statecharts: a visual formalism for complex systems
- Relationships between nondeterministic and deterministic tape complexities
- Decidability of Second-Order Theories and Automata on Infinite Trees
- On the complexity of verifying concurrent transition systems
- Automata, logics, and infinite games. A guide to current research
- A calculus of communicating systems
- Propositional dynamic logic of looping and converse is elementarily decidable
- Communicating sequential processes
- On the power of bounded concurrency II
- Modalities for model checking: Branching time logic strikes back
- On equations for regular languages, finite automata, and sequential networks
- On the power of bounded concurrency I
- Decision problems forω-automata
- Classes of Recursively Enumerable Sets and Their Decision Problems
- Complexity results for two-way and multi-pebble automata and their logics
- Alternation and bounded concurrency are reverse equivalent.
- Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
This page was built for publication: A Rice-style theorem for parallel automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1004287)
