| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 423358 | Electronic Notes in Theoretical Computer Science | 2010 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
