STORMED hybrid systems

Vladimeros Vladimerou; Pavithra Prabhakar; Mahesh Viswanathan; Geir Dullerud

doi:10.1007/978-3-540-70583-3_12

STORMED hybrid systems

Vladimeros Vladimerou, Pavithra Prabhakar, Mahesh Viswanathan, Geir Dullerud

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

Abstract

We introduce STORMED hybrid systems, a decidable class of hybrid systems which is similar to o-minimal hybrid automata in that the continuous dynamics and constraints are described in an o-minimal theory. However, unlike o-minimal hybrid automata, the variables are not initialized in a memoryless fashion at discrete steps. STORMED hybrid systems require flows which are monotonic with respect to some vector in the continuous space and can be characterised as bounded-horizon systems in terms of their discrete transitions. We demonstrate that such systems admit a finite bisimulation, which can be effectively constructed provided the o-minimal theory used to describe the system is decidable. As a consequence, many verification problems for such systems have effective decision algorithms.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages	136-147
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-540-70583-3_12
State	Published - Aug 14 2008
Event	35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland Duration: Jul 7 2008 → Jul 11 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	5126 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country	Iceland
City	Reykjavik
Period	7/7/08 → 7/11/08

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-70583-3_12

Fingerprint Dive into the research topics of 'STORMED hybrid systems'. Together they form a unique fingerprint.

Cite this

Vladimerou, V., Prabhakar, P., Viswanathan, M., & Dullerud, G. (2008). STORMED hybrid systems. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings (PART 2 ed., pp. 136-147). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5126 LNCS, No. PART 2). https://doi.org/10.1007/978-3-540-70583-3_12

STORMED hybrid systems. / Vladimerou, Vladimeros; Prabhakar, Pavithra; Viswanathan, Mahesh ; Dullerud, Geir.

Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 2. ed. 2008. p. 136-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5126 LNCS, No. PART 2).

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

Vladimerou, V, Prabhakar, P, Viswanathan, M & Dullerud, G 2008, STORMED hybrid systems. in Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 5126 LNCS, pp. 136-147, 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, 7/7/08. https://doi.org/10.1007/978-3-540-70583-3_12

Vladimerou V, Prabhakar P, Viswanathan M , Dullerud G. STORMED hybrid systems. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 2 ed. 2008. p. 136-147. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). https://doi.org/10.1007/978-3-540-70583-3_12

Vladimerou, Vladimeros ; Prabhakar, Pavithra ; Viswanathan, Mahesh ; Dullerud, Geir. / STORMED hybrid systems. Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 2. ed. 2008. pp. 136-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{60548d5e32f94d1cb786a519c2471b42,

title = "STORMED hybrid systems",

abstract = "We introduce STORMED hybrid systems, a decidable class of hybrid systems which is similar to o-minimal hybrid automata in that the continuous dynamics and constraints are described in an o-minimal theory. However, unlike o-minimal hybrid automata, the variables are not initialized in a memoryless fashion at discrete steps. STORMED hybrid systems require flows which are monotonic with respect to some vector in the continuous space and can be characterised as bounded-horizon systems in terms of their discrete transitions. We demonstrate that such systems admit a finite bisimulation, which can be effectively constructed provided the o-minimal theory used to describe the system is decidable. As a consequence, many verification problems for such systems have effective decision algorithms.",

author = "Vladimeros Vladimerou and Pavithra Prabhakar and Mahesh Viswanathan and Geir Dullerud",

year = "2008",

month = aug,

day = "14",

doi = "10.1007/978-3-540-70583-3_12",

language = "English (US)",

isbn = "3540705821",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "136--147",

booktitle = "Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings",

edition = "PART 2",

note = "35th International Colloquium on Automata, Languages and Programming, ICALP 2008 ; Conference date: 07-07-2008 Through 11-07-2008",

}

TY - GEN

T1 - STORMED hybrid systems

AU - Vladimerou, Vladimeros

AU - Prabhakar, Pavithra

AU - Viswanathan, Mahesh

AU - Dullerud, Geir

PY - 2008/8/14

Y1 - 2008/8/14

N2 - We introduce STORMED hybrid systems, a decidable class of hybrid systems which is similar to o-minimal hybrid automata in that the continuous dynamics and constraints are described in an o-minimal theory. However, unlike o-minimal hybrid automata, the variables are not initialized in a memoryless fashion at discrete steps. STORMED hybrid systems require flows which are monotonic with respect to some vector in the continuous space and can be characterised as bounded-horizon systems in terms of their discrete transitions. We demonstrate that such systems admit a finite bisimulation, which can be effectively constructed provided the o-minimal theory used to describe the system is decidable. As a consequence, many verification problems for such systems have effective decision algorithms.

AB - We introduce STORMED hybrid systems, a decidable class of hybrid systems which is similar to o-minimal hybrid automata in that the continuous dynamics and constraints are described in an o-minimal theory. However, unlike o-minimal hybrid automata, the variables are not initialized in a memoryless fashion at discrete steps. STORMED hybrid systems require flows which are monotonic with respect to some vector in the continuous space and can be characterised as bounded-horizon systems in terms of their discrete transitions. We demonstrate that such systems admit a finite bisimulation, which can be effectively constructed provided the o-minimal theory used to describe the system is decidable. As a consequence, many verification problems for such systems have effective decision algorithms.

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

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

U2 - 10.1007/978-3-540-70583-3_12

DO - 10.1007/978-3-540-70583-3_12

M3 - Conference contribution

AN - SCOPUS:49049107553

SN - 3540705821

SN - 9783540705826

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 136

EP - 147

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -