THERMOGAMAS - Robustness in Dynamical Systems: when allowing noise makes the undecidable decidable (Manon Blanc)

Talk given during the THERMOGAMAS Workshop.

Abstract: Reachability for dynamical systems evolving over the reals is undecidable. However, various results in the literature have shown that decision procedures exist when restricting to robust systems, provided a suitably chosen notion of robustness is employed. When infinitesimal perturbations are allowed, decision procedures for state reachability exist. More fundamentally, while all these statements are only about computability issues, we also consider complexity theory aspects. We prove that robustness to some precision is inherently related to the complexity of the decision procedure. We also give and prove two notions of robustness for tilesets in order to have a decidable Domino problem.