Reachability in tree-like component systems is PSPACE-complete


Majster-Cederbaum, Mila ; Semmelrock, Nils



DOI: https://doi.org/10.1016/j.entcs.2010.05.012
URL: http://www.sciencedirect.com/science/article/pii/S...
Additional URL: https://www.researchgate.net/publication/220368559...
Document Type: Conference or workshop publication
Year of publication: 2010
The title of a journal, publication series: Electronic Notes in Theoretical Computer Science : ENTCS
Volume: 263
Page range: 197-210
Conference title: 6th International Workshop, FACS 2009
Location of the conference venue: Eindhoven, The Netherlands
Date of the conference: 02.-03.11.2009
Place of publication: Amsterdam [u.a.]
Publishing house: Elsevier
ISSN: 1571-0661
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik II (Majster-Cederbaum Em)
Subject: 004 Computer science, internet
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: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.




+ Citation Example and Export

Majster-Cederbaum, Mila ; Semmelrock, Nils Reachability in tree-like component systems is PSPACE-complete. Electronic Notes in Theoretical Computer Science : ENTCS 263 197-210 (2010) Amsterdam [u.a.] 6th International Workshop, FACS 2009 (Eindhoven, The Netherlands) [Conference or workshop publication]


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



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


Actions (login required)

Show item Show item