Reachability in tree-like component systems is PSPACE-complete

Majster-Cederbaum, Mila ; Semmelrock, Nils

Additional URL:
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 -2005, 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.

Metadata export


+ 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