Deciding Liveness in Component-Based Systems is NP-hard
Moritz Martens, Christoph Minnameier, Mila Majster-Cederbaum · MADOC (University of Mannheim) · 2006
Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. In a system that has been shown to be deadlock-free one can ask if a set of components is live. We present here a polynomial time reduction from 3-SAT to the question whether a set of components is live in a deadlock-free system.