Local and global deadlock-detection in component-based systems are NP-hard |
| |
| Authors: | Christoph Minnameier |
| |
| Affiliation: | Institut für Informatik, Universität Mannheim, Germany |
| |
| 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. |
| |
| Keywords: | Computational complexity Concurrency Safety/security in digital systems |
| 本文献已被 ScienceDirect 等数据库收录！ |
