Skip to main content

A Semidecidable Procedure for Reachability Analysis of Piecewise Constant Derivative Systems

Dr. Olga Tveretina ( University of Hertfordshire )

This talk will focus on a class of hybrid systems called piecewise constant-derivative systems, for which the reachability problem has been proven decidable in two dimensions and undecidable in three or more dimensions. The decidability results for two dimensions rely on the existence of a periodic trajectory after a finite number of steps. The periodic trajectory does not generally exist in higher dimensions. Nevertheless, higher dimensional systems also feature a degree of regularity. I will introduce the notion of quasicycle that represents this kind of acyclic behaviour. I will show that certain types of quasicycle permit computation of exact reachable sets and will illustrate the effectiveness of my approach on some examples.

Speaker bio

Olga Tveretina is Senior Lecturer in the School of Computer Science at the University of Hertfordshire. She studied Applied Mathematics at Tomsk University in Russia and Tartu University in Estonia and received Ph.D. in Computer Science from Technical University of Eindhoven in the Netherlands. Olga's research interests include propositional proof complexity, decidability of the reachability problem for hybrid systems and decision procedures for software and hardware verification.

Share this: