Abstract | ||
---|---|---|
We study finite bisimulations of dynamical systems in ℝ 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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/s00224-007-9019-4 | Theory Comput. Syst. |
Keywords | Field | DocType |
Dynamical system,Hybrid system,Bisimulation,Semialgebraic geometry | Discrete mathematics,Parameterized complexity,Combinatorics,Exponential function,Upper and lower bounds,Dynamical systems theory,Bisimulation,Pfaffian,Mathematics,Double exponential function,Dynamical system | Journal |
Volume | Issue | ISSN |
43 | 3 | 1432-4350 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Margarita V. Korovina | 1 | 84 | 15.61 |
Nicolai Vorobjov | 2 | 288 | 41.45 |