A compositional algorithm for parallel model checking of polygonal hybrid systems. (English) Zbl 1168.68426

Pace, Gordon; Schneider, Gerardo

Barkaoui, Kamel (ed.) et al., Theoretical aspects of computing – ICTAC 2006. Third international colloquium, Tunis, Tunisia, November 20–24, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-48815-6/pbk). Lecture Notes in Computer Science 4281, 168-182 (2006).

Summary: The reachability problem as well as the computation of the phase portrait for the class of planar hybrid systems defined by constant differential inclusions (SPDI), has been shown to be decidable. The existing reachability algorithm is based on the exploitation of topological properties of the plane which are used to accelerate certain kind of cycles. The complexity of the algorithm makes the analysis of large systems generally unfeasible. In this paper we present a compositional parallel algorithm for reachability analysis of SPDIs. The parallelization is based on the qualitative information obtained from the phase portrait of an SPDI, in particular the controllability kernel.
For the entire collection see [Zbl 1142.68004].

MSC:

68Q60

Specification and verification (program logics, model checking, etc.)

Software:

SPeeDI