License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.32
URN: urn:nbn:de:0030-drops-128443
Go to the corresponding LIPIcs Volume Portal

Majumdar, Rupak ; Ouaknine, Joël ; Pouly, Amaury ; Worrell, James

Algebraic Invariants for Linear Hybrid Automata

LIPIcs-CONCUR-2020-32.pdf (0.6 MB)


We exhibit an algorithm to compute the strongest algebraic (or polynomial) invariants that hold at each location of a given guard-free linear hybrid automaton (i.e., a hybrid automaton having only unguarded transitions, all of whose assignments are given by affine expressions, and all of whose continuous dynamics are given by linear differential equations). Our main tool is a control-theoretic result of independent interest: given such a linear hybrid automaton, we show how to discretise the continuous dynamics in such a way that the resulting automaton has precisely the same algebraic invariants.

BibTeX - Entry

  author =	{Rupak Majumdar and Jo{\"e}l Ouaknine and Amaury Pouly and James Worrell},
  title =	{{Algebraic Invariants for Linear Hybrid Automata}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-128443},
  doi =		{10.4230/LIPIcs.CONCUR.2020.32},
  annote =	{Keywords: Hybrid automata, algebraic invariants}

Keywords: Hybrid automata, algebraic invariants
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI