Bounds on sizes of finite bisimulations of Pfaffian dynamical systems

M Korovina, Nicolai Vorobjov

Research output: Contribution to journalArticlepeer-review

Abstract

We study finite bisimulations of dynamical systems in R-n defined by Pfaffian maps. The pure existence of finite bisimulations for a more general class of o-minimal systems was shown in Brihaye et al. (Lecture Notes in Comput. Sci. 2993, 219-233, 2004), Davoren (Theor. Inf. Appl. 33(4/5), 357-382, 1999), Lafferriere et al. (Math. Control Signals Syst. 13, 1-21, 2000). In Lecture Notes in Comput. Sci. 3210, 2004, the authors proved a double exponential upper bound on the size of a bisimulation in terms of the size of description of the dynamical system. In the present paper we improve it to a single exponential upper bound, and show that this bound is tight, by exhibiting a parameterized class of systems on which it is attained.
Original languageEnglish
Pages (from-to)498-515
Number of pages18
JournalTheory of Computing Systems
Volume43
Issue number3-4
Early online date3 Jul 2007
DOIs
Publication statusPublished - 1 Dec 2008
Event2nd Conference on Computability in Europe - Swansea University, Department of Computer Science, Swansea, Wales, UK United Kingdom
Duration: 30 Jun 20065 Jul 2006

Keywords

  • Hybrid system
  • Dynamical system
  • Semialgebraic geometry
  • Bisimulation

Fingerprint

Dive into the research topics of 'Bounds on sizes of finite bisimulations of Pfaffian dynamical systems'. Together they form a unique fingerprint.

Cite this