Skip to Main content Skip to Navigation
New interface
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
Contributor : Stefan Haar Connect in order to contact the contributor
Submitted on : Thursday, January 10, 2013 - 7:48:45 PM
Last modification on : Thursday, January 20, 2022 - 4:13:07 PM


  • HAL Id : hal-00772632, version 1


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



Record views