On the decidability of the reachability problem for GSPDIs
Gerardo Schneider · NORA - Norwegian Open Research Archives · 2007
Polygonal hybrid systems (SPDIs) are a subclass of hybrid systems whose dynamics is dened by constant dierential inclusions, for which the reachability problem is decidable.The decidability result is based, among other things, on the fact that a trajectory cannot enter and leave a given region through the same edge.An SPDI satisfying the above restriction is said to have the goodness property.In a previous work we have given a misleading proof sketch of decidability of reachability for SPDIs when relaxing goodness.In this work we give a counter-example to such proof and we give an algorithm for semi-deciding reachability of such class of systems.for a region not satisfying the goodness criteria).In the left side of the gure we can see a good region, where the two vectors a and b determine the impossibility of a trajectory to enter and leave the region P through the same edge of the polygon delimiting the region.On the other hand, the gure on the right shows a bad region: Both e 2 and e 5 can be crossed in both directions by a trajectory entering and leaving P .