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 -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.

BASE: Majster-Cederbaum, Mila ; Semmelrock, Nils

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

Hits per month over past year

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

Show item