JCSE, vol. 3, no. 2, pp.73-87, 2009

DOI:

Ensuring Sound Numerical Simulation of Hybrid Automata

Yerang Hur Jae-Hwan Sim Jesung Kim Jin-Young Choi
Department of Computer and Information Science, University of Pennsylvania, USA|Department of Computer Science and Engineering, Korea University, Korea|Department of Computer and Information Science, University of Pennsylvania, USA|Department of Computer S

Abstract: A hybrid system is a dynamical system in which states can be changed continuously anddiscretely. Simulation based on numerical methods is the widely used technique for analyzingcomplicated hybrid systems. Numerical simulation of hybrid systems, however, is subject to twotypes of numerical errors: truncation error and round-off error. The effect of such errors canmake an impossible transition step to become possible during simulation, and thus, to generatea simulation behavior that is not allowed by the model. The possibility of an incorrectsimulation behavior reduces con.dence in simulation-based analysis since it is impossible toknow whether a particular simulation trace is allowed by the model or not. To address thisproblem, we define the notion of Instrumented Hybrid Automata (IHA), which considers theeffect of accumulated numerical errors on discrete transition steps. We then show how toconvert Hybrid Automata (HA) to IHA and prove that every simulation behavior of IHApreserves the discrete transition steps of some behavior in HA; that is, simulation of IHA issound with respect to HA.

Keyword: No keyword

Full Paper:   128 Downloads, 3946 View