Guaranteed Termination in the Verification of LTL Properties of Non-Linear Robust Discrete Time Hybrid Systems

We present a novel approach to the automatic verification and falsification of LTL requirements of non-linear discrete-time hybrid systems. The verification tool uses an interval-based constraint solver for non-linear robust constraints to compute incrementally refined abstractions. Although the problem is in general undecidable, we prove termination of abstraction refinement based verification and falsification of such properties for the class of non-linear robust discrete-time hybrid systems. We argue, that—in industrial practice—safety critical control applications give rise to hybrid systems that are robust. We give first results on the application of this approach to a variant of an aircraft collision avoidance protocol.