Everything Is PSPACE-Complete in Interaction Systems
DOI10.1007/978-3-540-85762-4_15zbMATH Open1161.68625OpenAlexW1530284785MaRDI QIDQ5505604FDOQ5505604
Authors: Christoph Minnameier, Mila Majster-Cederbaum 
Publication date: 27 January 2009
Published in: Theoretical Aspects of Computing - ICTAC 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85762-4_15
Recommendations
- Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
- Local and global deadlock-detection in component-based systems are NP-hard
- PSPACE-completeness of modular supervisory control problems
- Complexity results for reachability in cooperating systems and approximated reachability by abstract over-approximations
- PSPACE-completeness of majority automata networks
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Title not available (Why is that?)
- Ensuring Properties of Interaction Systems
- A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems
- Composition for component-based modeling
- Title not available (Why is that?)
- Component-Based Construction of Deadlock-Free Systems
- Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
- Contracts for BIP: Hierarchical Interaction Models for Compositional Verification
- Title not available (Why is that?)
- A component-based Petri net model for specifying and validating cooperative information systems
Cited In (5)
- Local and global deadlock-detection in component-based systems are NP-hard
- Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
- Cross-Checking - Enhanced Over-Approximation of the Reachable Global State Space of Component-Based Systems
- Rigorous development of component-based systems using component metadata and patterns
- Deadlock-freedom in component systems with architectural constraints
This page was built for publication: Everything Is PSPACE-Complete in Interaction Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5505604)
