Article ID Journal Published Year Pages File Type
428193 Information Processing Letters 2007 7 Pages PDF
Abstract

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. We present here a polynomial time reduction from 3-SAT to the question whether an interaction system contains deadlocks.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics