Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets

DOI10.1007/978-3-540-77566-9_30zbMath1133.68057OpenAlexW1874372619MaRDI QIDQ5448661

Christoph Minnameier, Mila E. Majster-Cederbaum

Publication date: 7 March 2008

Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_30

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (4)

Deadlock-freedom in component systems with architectural constraints ⋮ Robustness in Interaction Systems ⋮ A Rice-style theorem for parallel automata ⋮ Everything Is PSPACE-Complete in Interaction Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Composition for component-based modeling
• Local and global deadlock-detection in component-based systems are NP-hard
• Contracts for BIP: Hierarchical Interaction Models for Compositional Verification
• Component-Based Construction of Deadlock-Free Systems
• A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems

This page was built for publication: Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets