From Non-Zenoness Verification to Termination

Pierre Ganty, Samir Genaim, Ratan Lal and Pavithra Prabhakar

Abstract—We investigate the problem of verifying the absence of zeno executions in a hybrid system. A zeno execution is one in which there are infinitely many discrete transitions in a finite time interval. The presence of zeno executions poses challenges towards implementation and analysis of hybrid control systems. We present a simple transformation of the hybrid system which reduces the non-zenoness verification problem to the termination verification problem, that is, the original system has no zeno executions if and only if the transformed system has no non- terminating executions. This provides both theoretical insights and practical techniques for non-zenoness verification. Further, it also provides techniques for isolating parts of the hybrid system and its initial states which do not exhibit zeno executions. We illustrate the feasibility of our approach by applying it on hybrid system examples.

ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE), 2015
Download: BIB PS PDF