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

Mateus de Oliveira Oliveira, Olga Tveretina

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

12 Downloads (Pure)

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 (). Two closely related open problems are point-to-point and edge-to-edge reachability for . Building on our technique to establish decidability of mortality for , 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 [4]. 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.
Original languageEnglish
Title of host publicationHSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems
Subtitle of host publicationComputation and Control, Part of CPS-IoT Week 2022
PublisherACM Press
Number of pages10
ISBN (Electronic)9781450391962
DOIs
Publication statusPublished - 4 May 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/

Publication series

NameHSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022

Conference

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

Keywords

  • hybrid Systems
  • Decidability
  • Mortality
  • Reachability

Fingerprint

Dive into the research topics of 'Mortality and Edge-to-Edge Reachability are Decidable on Surfaces'. Together they form a unique fingerprint.

Cite this