Skip to Main content Skip to Navigation
Conference papers

Comparison of Algorithms for Checking Emptiness on Büchi Automata

Andreas Gaiser Stefan Schwoon 1
1 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
Abstract : We re-investigate the problem of LTL model-checking for finite-state systems. Typical solutions, like in Spin, work on the fly, reducing the problem to Buechi emptiness. This can be done in linear time, and a variety of algorithms with this property exist. Nonetheless, subtle design decisions can make a great difference to their actual performance in practice, especially when used on-the-fly. We compare a number of algorithms experimentally on a large benchmark suite, measure their actual run-time performance, and propose improvements. Compared with the algorithm implemented in Spin, our best algorithm is faster by about 33 % on average. We therefore recommend that, for on-the-fly explicit-state model checking, nested DFS should be replaced by better solutions.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00772632
Contributor : Stefan Haar <>
Submitted on : Thursday, January 10, 2013 - 7:48:45 PM
Last modification on : Monday, February 15, 2021 - 10:50:23 AM

Identifiers

  • HAL Id : hal-00772632, version 1

Citation

Andreas Gaiser, Stefan Schwoon. Comparison of Algorithms for Checking Emptiness on Büchi Automata. MEMICS, Nov 2009, Znojmo, Czech Republic. ⟨hal-00772632⟩

Share

Metrics

Record views

379