Deciding Liveness in Component-Based Systems is NP-hard

Vorschau

PDF
livenessnphard.pdf - Veröffentlichte Version
Download (128kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1316
URN:	urn:nbn:de:bsz:180-madoc-13166
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	2006
Titel einer Zeitschrift oder einer Reihe:	Manuskripte / Reihe Informatik
Band/Volume:	06-17
Ort der Veröffentlichung:	Mannheim
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC-Schriftenreihe:	Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	NP-hartes Problem , Komponente <Software> , Lebendigkeit <Informatik>
Freie Schlagwörter (Deutsch):	Komponenten , NP-Härte , Lebendigkeit
Freie Schlagwörter (Englisch):	Components , NP-hardness , liveness
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. 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.