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

Preview

PDF
Deadlock_Detection_in_Component_Based_Systems_is_NP_hard.pdf - Published
Download (142kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1309
URN:	urn:nbn:de:bsz:180-madoc-13093
Document Type:	Working paper
Year of publication:	2006
The title of a journal, publication series:	Technical Reports
Volume:	06-015
Place of publication:	Mannheim
Publication language:	English
Institution:	School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC publication series:	Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject:	004 Computer science, internet
Subject headings (SWD):	Komponente <Software> , Verklemmung , Komplexitätsklasse NP
Individual keywords (German):	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.
Additional information: