  Hybrid systems exhibit phenomena which do not occur in systems with
continuous vector fields. One such phenomenon - Zeno executions - is
characterized by an infinite number of discrete events or transitions occurring
over a finite interval of time. This phenomenon is not necessarily undesirable
and may indeed be used to capture physical phenomena. In this paper, we examine
the problem of proving the existence and stability of zero executions. Our
approach is to develop a polynomial-time algorithm - based on the
sum-of-squares methodology - for verifying the stability of a Zeno execution.
We begin by stating Lyapunov-like theorems for local Zeno stability based on
existing results. Then, for hybrid systems with polynomial vector fields, we
use polynomial Lyapunov functions and semialgebraic geometry
(Positivstellensatz results) to reduce the local Lyapunov-like conditions to a
convex feasibility problem in polynomial variables. The feasibility problem is
then tested using an algorithm for sum-of-squares programming - SOSTOOLS. We
also extend these results to hybrid system with parametric uncertainty, where
the uncertain parameters lie in a semialgebriac set. We also provide several
examples illustrating the use of our technique.
