UNIVERSITY OF HERTFORDSHIRE
             COMPUTER SCIENCE RESEARCH COLLOQUIUM

                            presents

      "When are Mortality and Reachability Problems Decidable?"

                       Dr. Olga Tveretina
      (School of Physics, Engineering, and Computer Science,
                   University of Hertfordshire)

                     19 May 2021 (Wednesday)
                          13:00 -14:00

                  Everyone is Welcome to Attend

                          (over Zoom)

Abstract:

One of the most fundamental computational problems in dynamical system theory is the mortality problem which can be stated as follows: Given the specification of a dynamical system S, is it the case that all trajectories in S are mortal? Closely related to mortality is the reachability problem: Is a certain final state reachable from a certain initial state?  

The study of mortality and reachability have played a central role in many areas of computer science and applications. The mortality problem is relevant to the field of program termination, and it has been studied in different contexts and in different variants. The reachability problem is relevant to the area of formal verification.  

Both problems are known to be computationally difficult and undecidable in general, where decidability means the existence of an effective method (algorithm) that can provide a correct answer to the problem. 

In this talk, I will discuss the frontiers (including recent results) of decidability of mortality and reachability for some dynamical systems paying attention to systems on manifolds (surfaces).  

Finally, systems on manifolds have important practical applications. Areas, where surfaces arise, include among others biological systems (modelling processes on cell membranes), robotics (the configuration space of a robotic arm) and learning algorithms (finding a low-dimensional parameterization of high-dimensional data). 



---------------------------------------------------
Hertfordshire Computer Science Research Colloquium
http://cs-colloq.cs.herts.ac.uk