University of Hertfordshire

By the same authors

Deciding Reachability for Piecewise Constant Derivative Systems on Orientable Manifolds

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

View graph of relations
Original languageEnglish
Title of host publicationReachability Problems - 13th International Conference, RP 2019, Proceedings
EditorsEmmanuel Filiot, Raphaël Jungers, Igor Potapov
PublisherSpringer
Pages178-192
Number of pages15
Volume11674
ISBN (Electronic)9783030308063
ISBN (Print)9783030308056
DOIs
Publication statusPublished - 6 Sep 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11674

Abstract

A hybrid automaton is a finite state machine combined with some k real-valued continuous variables, where k determines the number of the automaton dimensions. This formalism is widely used for modelling safety-critical systems, and verification tasks for such systems can often be expressed as the reachability problem for hybrid automata. Asarin, Mysore, Pnueli and Schneider defined classes of hybrid automata lying on the boundary between decidability and undecidability in their seminal paper ‘Low dimensional hybrid systems - decidable, undecidable, don’t know’ [9]. They proved that certain decidable classes become undecidable when given a little additional computational power, and showed that the reachability question remains unsolved for some 2-dimensional systems. Piecewise Constant Derivative Systems on 2-dimensional manifolds (or PCD2m) constitute a class of hybrid automata for which decidability of the reachability problem is unknown. In this paper we show that the reachability problem becomes decidable for PCD2m if we slightly limit their dynamics, and thus we partially answer the open question of Asarin, Mysore, Pnueli and Schneider posed in [9].

Notes

© 2019 Springer-Verlag. This is a post-peer-review, pre-copyedit version of a paper published in Reachability Problems: 13th International Conference, RP 2019, Brussels, Belgium, September 11–13, 2019, Proceedings. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-30806-3_14

ID: 17705450