Reachability in Tree-Like Component Systems is PSPACE-Complete
Mila Majster-Cederbaum, Nils Semmelrock · Electronic Notes in Theoretical Computer Science · 2010
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.