License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.78
URN: urn:nbn:de:0030-drops-33619
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3361/
Go to the corresponding LIPIcs Volume Portal

Herbreteau, Frédéric ; Kini, Dileep ; Srivathsan, B. ; Walukiewicz, Igor

Using non-convex approximations for efficient analysis of timed automata

pdf-format:
43.pdf (0.5 MB)

Abstract

The reachability problem for timed automata asks if there exists a
path from an initial state to a target state. The standard
solution to this problem involves computing the zone graph of the
automaton, which in principle could be infinite. In order to make
the graph finite, zones are approximated using an extrapolation
operator. For reasons of efficiency in current algorithms
extrapolation of a zone is always a zone; and in particular it
is convex.

In this paper, we propose to solve the reachability problem without
such extrapolation operators. To ensure termination, we provide an
efficient algorithm to check if a zone is included in the so
called region closure of another. Although theoretically better,
closure cannot be used in the standard algorithm since a closure of
a zone may not be convex.

An additional benefit of the proposed approach is that it permits to
calculate approximating parameters on-the-fly during exploration of
the zone graph, as opposed to the current methods which do it by a
static analysis of the automaton prior to the exploration. This
allows for further improvements in the algorithm. Promising
experimental results are presented.

BibTeX - Entry

@InProceedings{herbreteau_et_al:LIPIcs:2011:3361,
  author =	{Fr{\'e}d{\'e}ric Herbreteau and Dileep Kini and B. Srivathsan and Igor Walukiewicz},
  title =	{{Using non-convex approximations for efficient analysis of timed automata}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{78--89},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3361},
  URN =		{urn:nbn:de:0030-drops-33619},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.78},
  annote =	{Keywords: Timed Automata, Model-checking, Non-convex abstraction, On-the-fly abstraction}
}

Keywords: Timed Automata, Model-checking, Non-convex abstraction, On-the-fly abstraction
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

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