Composing semi-algebraic O-minimal automata

A. Casagrande, P. Corvaja, C. Piazza, B. Mishra

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

Abstract

This paper addresses questions regarding the decidability of hybrid automata that may be constructed hierarchically and in a modular way, as is the case in many exemplar systems, be it natural or engineered. Since an important step in such constructions is a product operation, which constructs a new product hybrid automaton by combining two simpler component hybrid automata, an essential property that would be desired is that the reachability property of the product hybrid automaton be decidable, provided that the component hybrid automata belong to a suitably restricted family of automata. Somewhat surprisingly, the product operation does not assure a closure of decidability for the reachability problem. Nonetheless, this paper establishes the decidability of the reachability condition over automata which are obtained by composing two semi-algebraic o-minimal systems. The class of semi-algebraic o-minimal automata is not even closed under composition, i.e., the product of two automata of this class is not necessarily a semi-algebraic o-minimal automaton. However, we can prove our decidability result combining the decidability of both semi-algebraic formulae over the reals and linear Diophantine equations. All the proofs of the results presented in this paper can be found in [1].

Original languageEnglish (US)
Title of host publicationHybrid Systems
Subtitle of host publicationComputation and Control - 10th International Conference, HSCC 2007, Proceedings
PublisherSpringer Verlag
Pages668-671
Number of pages4
ISBN (Print)9783540714927
DOIs
StatePublished - 2007
Event10th International Conference on Hybrid Systems: Computation and Control, HSCC 2007 - Pisa, Italy
Duration: Apr 3 2007Apr 5 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4416 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Conference on Hybrid Systems: Computation and Control, HSCC 2007
CountryItaly
CityPisa
Period4/3/074/5/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Composing semi-algebraic O-minimal automata'. Together they form a unique fingerprint.

  • Cite this

    Casagrande, A., Corvaja, P., Piazza, C., & Mishra, B. (2007). Composing semi-algebraic O-minimal automata. In Hybrid Systems: Computation and Control - 10th International Conference, HSCC 2007, Proceedings (pp. 668-671). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4416 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-71493-4_57