Show simple item record

dc.contributor.authorSandler, Andrei
dc.contributor.authorTveretina, Olga
dc.contributor.editorFiliot, Emmanuel
dc.contributor.editorJungers, Raphaël
dc.contributor.editorPotapov, Igor
dc.identifier.citationSandler , A & Tveretina , O 2019 , Deciding Reachability for Piecewise Constant Derivative Systems on Orientable Manifolds . in E Filiot , R Jungers & I Potapov (eds) , Reachability Problems - 13th International Conference, RP 2019, Proceedings . vol. 11674 , Lecture Notes in Computer Science , vol. 11674 , Springer , pp. 178-192 .
dc.identifier.otherPURE: 17705450
dc.identifier.otherPURE UUID: 6d1bdccf-1a4b-41f9-ae44-6b4d2431a7d8
dc.identifier.otherScopus: 85072867688
dc.description© 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:
dc.description.abstractA 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].en
dc.relation.ispartofReachability Problems - 13th International Conference, RP 2019, Proceedings
dc.relation.ispartofseriesLecture Notes in Computer Science
dc.subjectHybrid Systems, reachability, decidability
dc.subjectHybrid systems
dc.subjectComputer Science(all)
dc.subjectComputational Theory and Mathematics
dc.subjectTheoretical Computer Science
dc.titleDeciding Reachability for Piecewise Constant Derivative Systems on Orientable Manifoldsen
dc.contributor.institutionSchool of Engineering and Computer Science
dc.contributor.institutionDepartment of Computer Science
dc.relation.schoolSchool of Engineering and Computer Science
dc.description.versiontypeFinal Accepted Version

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record