Everything Is PSPACE-Complete in Interaction Systems

DOI10.1007/978-3-540-85762-4_15MaRDI QIDQ5505604zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1693513 (Why is no real title available?)
• scientific article; zbMATH DE number 4110131 (Why is no real title available?)
• scientific article; zbMATH DE number 1354143 (Why is no real title available?)
• A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems
• A component-based Petri net model for specifying and validating cooperative information systems
• Component-Based Construction of Deadlock-Free Systems
• Composition for component-based modeling
• Contracts for BIP: Hierarchical Interaction Models for Compositional Verification
• Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
• Ensuring Properties of Interaction Systems
• Relationships between nondeterministic and deterministic tape complexities

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)