Decidability and Undecidability in Hybrid Systems
- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- November 15, **1:00** P.M.
Abstract:
The analysis of the behavior of dynamical systems consisting of
a mixture of discrete and continuous variables has become an
active research area due to the proliferation of hybrid systems
into everyday life. Beside the practical motivations, the interaction
between the discrete and the continuous might shed a new light
on each of the disciplines.
In this talk I will discuss a class of simple hybrid dynamical systems
(systems with piecewise-constant derivatives) and present some results
concerning the decidability of the reachability problem for such
systems (i.e., decide whether there is a trajectory connecting to
given points). In particular I will show:
- The problem is decidable for two-dimensional systems (joint work with
A. Pnueli)
- The problem is undecidable for three or more dimensions via simulation
of 2PDAs (joint work with E. Asarin).
- The problem is highly undecidable: by adding few dimensions at a time
one can climb up indefinitely in the arithmetical hierarchy. In other words,
for every arithmetical problem one can construct a system that ``solves''
it (with the help of Zeno's paradox). (E. Asarin)