Deciding Liveness in Component-Based Systems is NP-hard


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


[img]
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: 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 Mathematik und Informatik
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.

Dieser Eintrag ist Teil der Universitätsbibliographie.

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




+ Zitationsbeispiel und Export

Martens, Moritz und Minnameier, Christoph und Majster-Cederbaum, Mila (2006) Deciding Liveness in Component-Based Systems is NP-hard. Mannheim [Arbeitspapier]
[img]
Vorschau



+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detailierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen