Reachability in Tree-Like Component Systems is PSPACE-Complete


Semmelrock, Nils ; Majster-Cederbaum, Mila


[img]
Preview
PDF
TreeLike.pdf - Published

Download (629kB)

URL: http://ub-madoc.bib.uni-mannheim.de/2346
URN: urn:nbn:de:bsz:180-madoc-23464
Document Type: Working paper
Year of publication: 2009
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): 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.




+ Citation Example and Export

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