Deciding Liveness in Component-Based Systems is NP-hard


Martens, Moritz ; Minnameier, Christoph ; Majster-Cederbaum, Mila


[img]
Preview
PDF
livenessnphard.pdf - Published

Download (128kB)

URL: https://ub-madoc.bib.uni-mannheim.de/1316
URN: urn:nbn:de:bsz:180-madoc-13166
Document Type: Working paper
Year of publication: 2006
The title of a journal, publication series: Manuskripte / Reihe Informatik
Volume: 06-17
Place of publication: Mannheim
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Mathematik und Informatik
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): NP-hartes Problem , Komponente <Software> , Lebendigkeit <Informatik>
Individual keywords (German): Komponenten , NP-Härte , Lebendigkeit
Keywords (English): 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.

Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Martens, Moritz ; Minnameier, Christoph ; Majster-Cederbaum, Mila (2006) Deciding Liveness in Component-Based Systems is NP-hard. Open Access Manuskripte / Reihe Informatik Mannheim 06-17 [Working paper]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item