Local and global deadlock-detection in component-based systems are NP-hard

DOI10.1016/J.IPL.2007.02.016MaRDI QIDQ2379953zbMATH OpenOpenAlexFDO

Authors Christoph Minnameier

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.02.016

zbMATH Keywords

computational complexityconcurrencysafety/security in digital systems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems
• Everything Is PSPACE-Complete in Interaction Systems
• On the complexity of deadlock detection in families of planar nets
• scientific article; zbMATH DE number 3926230
• scientific article; zbMATH DE number 177258

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 944424 (Why is no real title available?)
• A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems
• Component-Based Construction of Deadlock-Free Systems
• Composition for component-based modeling
• The complexity of theorem-proving procedures

Cited in

(4)

• Everything Is PSPACE-Complete in Interaction Systems
• Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
• A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems
• Rigorous development of component-based systems using component metadata and patterns

This page was built for publication: Local and global deadlock-detection in component-based systems are NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379953)