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...
Weitere URL:	https://www.researchgate.net/publication/220368559...
Dokumenttyp:	Konferenzveröffentlichung
Erscheinungsjahr:	2010
Titel einer Zeitschrift oder einer Reihe:	Electronic Notes in Theoretical Computer Science : ENTCS
Band/Volume:	263
Seitenbereich:	197-210
Veranstaltungstitel:	6th International Workshop, FACS 2009
Veranstaltungsort:	Eindhoven, The Netherlands
Veranstaltungsdatum:	02.-03.11.2009
Ort der Veröffentlichung:	Amsterdam [u.a.]
Verlag:	Elsevier
ISSN:	1571-0661
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Praktische Informatik II (Majster-Cederbaum -2005, Em)
Fachgebiet:	004 Informatik
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.
Zusätzliche Informationen:	Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.

BASE: Majster-Cederbaum, Mila ; Semmelrock, Nils

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

Aufrufe im letzten Jahr

Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail

Eintrag anzeigen