University of Hertfordshire

By the same authors

Mortality and Edge-to-Edge Reachability are Decidable on Surfaces

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Documents

View graph of relations
Original languageEnglish
Title of host publicationThe proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control.
PublisherACM Digital Library
Publication statusAccepted/In press - 17 Jan 2022
EventHSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control - Milan, Italy
Duration: 4 May 20226 May 2022
https://hscc.acm.org/2022/

Conference

ConferenceHSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control
Country/TerritoryItaly
CityMilan
Period4/05/226/05/22
Internet address

Abstract

The mortality problem for a given dynamical system S consists of determining whether every trajectory of S eventually halts. In this work, we show that this problem is decidable for the class of piecewise constant derivative systems on two-dimensional manifolds, also called surfaces (PCDm). Two closely related open problems are point-to-point and edge-to-edge reachability for PCDm.

Building on our technique to establish decidability of mortality for PCDm, we show that the edge-to-edge reachability problem for these systems is also decidable. In this way we solve the edge-to-edge reachability case of an open problem due to Asarin, Mysore, Pnueli and Schneider. This implies that the interval-to-interval version of the classical open problem of reachability for regular piecewise affine maps (PAMs) is also decidable. In other words, point-to-point reachability for regular PAMs can be effectively approximated with arbitrarily precision.

ID: 26723584