Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2544
Authors: Schwoon, Stefan
Esparza, Javier
Title: A note on on-the-fly verification algorithms
Issue Date: 2004
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2004,6
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-22281
http://elib.uni-stuttgart.de/handle/11682/2561
http://dx.doi.org/10.18419/opus-2544
Abstract: The automata-theoretic approach to verification of LTL relies on an algorithm for finding accepting cycles in the product of the system and a Büchi automaton for the negation of the formula. Explicit-state model checkers typically construct the product space "on the fly" and explore the states using depth-first search. We survey algorithms proposed for this purpose and propose two improved algorithms, one based on nested DFS, the other on strongly connected components. We compare these algorithms both theoretically and experimentally and determine cases where both algorithms can be useful.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2004_06.pdf179,47 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.