Reachability in tree-like component systems is PSPACE-complete

Semmelrock, Nils ; Majster-Cederbaum, Mila

Preview

PDF
TreeLike.pdf - Published
Download (629kB)

URL:	https://madoc.bib.uni-mannheim.de/2346
URN:	urn:nbn:de:bsz:180-madoc-23464
Document Type:	Working paper
Year of publication:	2009
The title of a journal, publication series:	None
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):	PSPACE
Keywords (English):	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.
Additional information:

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

BASE: Semmelrock, Nils ; Majster-Cederbaum, Mila

Google Scholar: Semmelrock, Nils ; Majster-Cederbaum, Mila

Downloads per month over past year

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

Show item