### 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,131). 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.

Original language | English |
---|---|

Title of host publication | Logical Approaches to Computational Barriers, Proceedings |

Pages | 267-276 |

Number of pages | 10 |

Volume | 3988 |

Publication status | Published - 2006 |

### Publication series

Name | Lecture Notes in Computer Science |
---|

## Fingerprint Dive into the research topics of 'Upper and lower bounds on sizes of finite bisimulations of Pfaffian hybrid systems'. Together they form a unique fingerprint.

## Cite this

Korovina, M., & Vorobjov, N. (2006). Upper and lower bounds on sizes of finite bisimulations of Pfaffian hybrid systems. In

*Logical Approaches to Computational Barriers, Proceedings*(Vol. 3988, pp. 267-276). (Lecture Notes in Computer Science).