Lower and Upper Bounds in Zone-Based Abstractions of Timed Automata

PELÁNEK, Radek, Kim G. LARSEN, Gerd BEHRMANN and Patricia BOUYER. Lower and Upper Bounds in Zone-Based Abstractions of Timed Automata. International Journal on Software Tools for Technology Transfer (STTT). Springer-Verlag GmbH, 2006, vol. 8, No 3, p. 204-215. ISSN 1433-2779.

Basic information

Original name

Lower and Upper Bounds in Zone-Based Abstractions of Timed Automata

Name in Czech

Využití horních a dolních mezí při zónových abstrakcích časových automatů

Authors

PELÁNEK, Radek (203 Czech Republic, guarantor), Kim G. LARSEN (208 Denmark), Gerd BEHRMANN (208 Denmark) and Patricia BOUYER (250 France)

Edition

International Journal on Software Tools for Technology Transfer (STTT), Springer-Verlag GmbH, 2006, 1433-2779

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14330/06:00015564

Organization unit

Faculty of Informatics

Keywords in English

model checking; timed automata; verification; abstraction; extrapolation

Tags

Abstraction, extrapolation, Model checking, timed automata, verification

Tags

International impact, Reviewed

---

Abstract

V originále

Timed automata have an infinite semantics. For verification purposes, one usually uses zone based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds, significantly coarser abstractions can be obtained. We show soundness and completeness of the new abstractions w.r.t. reachability. We demonstrate how information about lower and upper bounds can be used to optimise the algorithm for bringing a difference bound matrix into normal form. Finally, we experimentally demonstrate that the new techniques dramatically increases the scalability of the real-time model checker Uppaal.

In Czech

Časové automaty mají nekonečnou sémantiku. Pro účely verifikace se většinou používá abstrakce založená na zónách braných vzhledem k maximálním konstantám objevujícím se v časovém automatu. Ukazujeme, že rozlišením maximálních spodních a horním mezí lze dosáhnou významně hrubších abstrakcí. Dále předvádíme, jak může být informace o maximálních horních a dolních mezích využita pro kanonizaci matice rozdílů. Také experimentálně prokazujeme, že tato nová technika výrazně vylepší výkon nástroje UPPAAL.

---

Links

GA201/03/0509, research and development project	Name: Automatizovaná verifikace paralelních a distribuovaných systémů Investor: Czech Science Foundation, Automated Verification of Parallel and Distributed Systems
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science