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

Mateus de Oliveira Oliveira; Olga Tveretina

doi:10.1145/3501710.3519529

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

Mateus de Oliveira Oliveira, Olga Tveretina

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

21 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 language	English
Title of host publication	HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems
Subtitle of host publication	Computation and Control, Part of CPS-IoT Week 2022
Publisher	ACM Press
Number of pages	10
ISBN (Electronic)	9781450391962
DOIs	https://doi.org/10.1145/3501710.3519529
Publication status	Published - 4 May 2022
Event	HSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control - Milan, Italy Duration: 4 May 2022 → 6 May 2022 https://hscc.acm.org/2022/

Publication series

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

Conference

Conference	HSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control
Country/Territory	Italy
City	Milan
Period	4/05/22 → 6/05/22
Internet address	https://hscc.acm.org/2022/

Keywords

hybrid Systems
Decidability
Mortality
Reachability

Access to Document

10.1145/3501710.3519529

Final_Version
© 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is an open access paper distributed under the Creative Commons Attribution License, to view a copy of the license, see: https://creativecommons.org/licenses/by/4.0/
Final published version, 733 KBLicence: CC BY

Cite this

de Oliveira Oliveira, M., & Tveretina, O. (2022). Mortality and Edge-to-Edge Reachability are Decidable on Surfaces. In HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022 Article 16 (HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022). ACM Press. https://doi.org/10.1145/3501710.3519529

de Oliveira Oliveira, Mateus ; Tveretina, Olga. / Mortality and Edge-to-Edge Reachability are Decidable on Surfaces. HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022. ACM Press, 2022. (HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022).

@inproceedings{1304fab0196b45538f0ff591a6c7af7d,

title = "Mortality and Edge-to-Edge Reachability are Decidable on Surfaces",

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.",

keywords = "hybrid Systems, Decidability, Mortality, Reachability",

author = "{de Oliveira Oliveira}, Mateus and Olga Tveretina",

note = "{\textcopyright} 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is an open access paper distributed under the Creative Commons Attribution License, to view a copy of the license, see: https://creativecommons.org/licenses/by/4.0/; HSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control ; Conference date: 04-05-2022 Through 06-05-2022",

year = "2022",

month = may,

day = "4",

doi = "10.1145/3501710.3519529",

language = "English",

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

publisher = "ACM Press",

booktitle = "HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems",

address = "United States",

url = "https://hscc.acm.org/2022/",

}

de Oliveira Oliveira, M & Tveretina, O 2022, Mortality and Edge-to-Edge Reachability are Decidable on Surfaces. in HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022., 16, HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022, ACM Press, HSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control, Milan, Italy, 4/05/22. https://doi.org/10.1145/3501710.3519529

Mortality and Edge-to-Edge Reachability are Decidable on Surfaces. / de Oliveira Oliveira, Mateus; Tveretina, Olga.
HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022. ACM Press, 2022. 16 (HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - de Oliveira Oliveira, Mateus

AU - Tveretina, Olga

N1 - © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is an open access paper distributed under the Creative Commons Attribution License, to view a copy of the license, see: https://creativecommons.org/licenses/by/4.0/

PY - 2022/5/4

Y1 - 2022/5/4

N2 - 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.

AB - 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.

KW - hybrid Systems

KW - Decidability

KW - Mortality

KW - Reachability

UR - http://www.scopus.com/inward/record.url?scp=85130857706&partnerID=8YFLogxK

U2 - 10.1145/3501710.3519529

DO - 10.1145/3501710.3519529

M3 - Conference contribution

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

BT - HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems

PB - ACM Press

T2 - HSCC 2022 : 25th ACM International Conference on Hybrid Systems: Computation and Control

Y2 - 4 May 2022 through 6 May 2022

ER -

de Oliveira Oliveira M, Tveretina O. Mortality and Edge-to-Edge Reachability are Decidable on Surfaces. In HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022. ACM Press. 2022. 16. (HSCC 2022 - Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control, Part of CPS-IoT Week 2022). doi: 10.1145/3501710.3519529

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this