Reachability in Cooperating Systems with Architectural Constraints is PSPACE-Complete

Mila Majster-Cederbaum
(University Mannheim)
Nils Semmelrock
(University Mannheim)

The reachability problem in cooperating systems is known to be PSPACE-complete. We show here that this problem remains PSPACE-complete when we restrict the communication structure between the subsystems in various ways. For this purpose we introduce two basic and incomparable subclasses of cooperating systems that occur often in practice and provide respective reductions. The subclasses we consider consist of cooperating systems the communication structure of which forms a line respectively a star.

In Anton Wijs, Dragan Bošnački and Stefan Edelkamp: Proceedings 2nd Workshop on GRAPH Inspection and Traversal Engineering (GRAPHITE 2013), Rome, Italy, March 24, 2013, Electronic Proceedings in Theoretical Computer Science 138, pp. 1–11.
Published: 30th December 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.138.1 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org