Paper Info
Title
Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Hybrid Systems
Abstract
In this paper we study a class of hybrid systems defined by Pfaffian maps. It is a sub-class of o-minimal hybrid systems which capture rich continuous dynamics and yet can be studied using finite bisimulations. The existence of finite bisimulations for o-minimal dynamical and hybrid systems has been shown by several authors (see e.g. [3,4,13]). The next natural question to investigate is how the sizes of such bisimulations can be bounded. The first step in this direction was done in [10] where a double exponential upper bound was shown for Pfaffian dynamical and hybrid systems. In the present paper we improve this bound to a single exponential upper bound. Moreover we show that this bound is tight in general, by exhibiting a parameterized class of systems on which the exponential bound is attained. The bounds provide a basis for designing efficient algorithms for computing bisimulations, solving reachability and motion planning problems.
Year
DOI
Venue
2006
10.1007/11780342_28
CiE
Keywords
Field
DocType
hybrid system,upper and lower bounds,upper bound,motion planning
Discrete mathematics,Combinatorics,Parameterized complexity,Exponential function,Upper and lower bounds,Pfaffian,Hybrid system,Mathematics,Double exponential function,Dynamical system,Bounded function
Conference
Volume
ISSN
ISBN
3988
0302-9743
3-540-35466-2
Citations 
PageRank 
References 
11
0.82
9
Authors
2
Name
Order
Citations
PageRank
Margarita V. Korovina18415.61
Nicolai Vorobjov228841.45