Reachability in Tree-Like Component Systems is PSPACE-Complete


Semmelrock, Nils ; Majster-Cederbaum, Mila


[img]
Vorschau
PDF
TreeLike.pdf - Veröffentlichte Version

Download (629kB)

URL: http://ub-madoc.bib.uni-mannheim.de/2346
URN: urn:nbn:de:bsz:180-madoc-23464
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2009
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): PSPACE
Freie Schlagwörter (Englisch): Component Based , Architectural Constraints
Abstract: The reachability problem in component systems is PSPACE-complete. We show here that even the reachability problem in the subclass of component systems with "tree-like'' communication is PSPACE-complete. For this purpose we reduce the question if a Quantified Boolean Formula (QBF) is true to the reachability problem in "tree-like'' component systems.
Zusätzliche Informationen:

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




+ Zitationsbeispiel und Export

Semmelrock, Nils ; Majster-Cederbaum, Mila (2009) Reachability in Tree-Like Component Systems is PSPACE-Complete. Open Access [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