Deadlock-Detection in Component-Based Systems is NP-hard.

Vorschau

PDF
Deadlock_Detection_in_Component_Based_Systems_is_NP_hard.pdf - Veröffentlichte Version
Download (142kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1309
URN:	urn:nbn:de:bsz:180-madoc-13093
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	2006
Titel einer Zeitschrift oder einer Reihe:	Technical Reports
Band/Volume:	06-015
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):	Komponente <Software> , Verklemmung , Komplexitätsklasse NP
Freie Schlagwörter (Deutsch):	Deadlock-Detection, Component-Based Systems
Abstract:	We present a polynomial-time reduction from 3-SAT to DLIS, where DLIS is the set of interaction systems for which a deadlock-state is reachable.
Zusätzliche Informationen: