Deciding Reachability for 3-Dimensional Multi-Linear Systems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

82 Downloads (Pure)


This paper deals with the problem of point-to-point reachability in multi-linear systems. These systems consist of a partition of the Euclidean space into a finite number of regions and a constant derivative assigned to each region in the partition, which governs the dynamical behavior of the system within it. The reachability problem for multi-linear systems has been proven to be decidable for the two-dimensional case and undecidable for the dimension three and higher. Multi-linear systems however exhibit certain properties that make them very suitable for topological analysis. We prove that reachability can be decided exactly in the 3-dimensional case when systems satisfy certain conditions.
We show with experiments that our approach can be orders of magnitude more efficient than simulation
Original languageEnglish
Title of host publicationProcs of 2nd Int Symposium on Games, Automata, Logics and Formal Verification
Subtitle of host publicationGandALF 2011
PublisherElectronic Proceedings in Theoretical Computer Science
Publication statusPublished - 2011


  • Hybrid systems, the reachability problem, decidability


Dive into the research topics of 'Deciding Reachability for 3-Dimensional Multi-Linear Systems'. Together they form a unique fingerprint.

Cite this