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.




Metadaten-Export


Zitation


+ Suche Autoren in

+ Aufruf-Statistik

Aufrufe im letzten Jahr

Detaillierte Angaben



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


Actions (login required)

Eintrag anzeigen Eintrag anzeigen