Multi-Core Emptiness Checking of Timed Büchi Automata using Inclusion Abstraction

Alfons Laarman, Mads Chr. Olesen, Andreas Dalsgaard, Kim G. Larsen, Jaco van de Pol

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

16 Citations (Scopus)
353 Downloads (Pure)

Abstract

This paper contributes to the multi-core model checking of timed automata (TA) with respect to liveness properties, by investigating checking of TA Büchi emptiness under the very coarse inclusion abstraction or zone subsumption, an open problem in this field.

We show that in general Büchi emptiness is not preserved under this abstraction, but some other structural properties are preserved. Based on those, we propose a variation of the classical nested depth-first search (NDFS) algorithm that exploits subsumption. In addition, we extend the multi-core cndfs algorithm with subsumption, providing the first parallel LTL model checking algorithm for timed automata.

The algorithms are implemented in LTSmin, and experimental evaluations show the effectiveness and scalability of both contributions: subsumption halves the number of states in the real-world FDDI case study, and the multi-core algorithm yields speedups of up to 40 using 48 cores.
Original languageEnglish
Title of host publicationProceedings of the 25th International Conference on Computer Aided Verification (CAV)
Number of pages16
Volume8044
PublisherSpringer Publishing Company
Publication date2013
Pages968-983
ISBN (Print)978-3-642-39798-1
ISBN (Electronic)978-3-642-39799-8
DOIs
Publication statusPublished - 2013
Event25th International Concerence on Computer Aided Verification - Saint Petersburg, Russian Federation
Duration: 13 Jul 201319 Jul 2013
Conference number: 25th

Conference

Conference25th International Concerence on Computer Aided Verification
Number25th
CountryRussian Federation
CitySaint Petersburg
Period13/07/201319/07/2013
SeriesLecture Notes in Computer Science
Volume8044
ISSN0302-9743

Cite this

Laarman, A., Olesen, M. C., Dalsgaard, A., Larsen, K. G., & Pol, J. V. D. (2013). Multi-Core Emptiness Checking of Timed Büchi Automata using Inclusion Abstraction. In Proceedings of the 25th International Conference on Computer Aided Verification (CAV) (Vol. 8044, pp. 968-983). Springer Publishing Company. Lecture Notes in Computer Science, Vol.. 8044 https://doi.org/10.1007/978-3-642-39799-8_69