Reachability in tree-like component systems is PSPACE-complete

Semmelrock, Nils ; Majster-Cederbaum, Mila

Vorschau

PDF
TreeLike.pdf - Veröffentlichte Version
Download (629kB)

URL:	https://madoc.bib.uni-mannheim.de/2346
URN:	urn:nbn:de:bsz:180-madoc-23464
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	2009
Titel einer Zeitschrift oder einer Reihe:	None
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):	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.

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

Downloads im letzten Jahr

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

Eintrag anzeigen