I/O Efficient Accepting Cycle Detection

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BARNAT Jiří BRIM Luboš ŠIMEČEK Pavel

Year of publication 2007
Type Article in Proceedings
Conference 19th International Conference on Computer Aided Verification
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords I/O efficient; accepting cycle detection
Description We show how to adapt an existing non-DFS-based accepting cycle detection algorithm OWCTY [10,15,29] to the I/O efficient setting and compare its I/O efficiency and practical performance to the existing I/O efficient LTL model checking approach of Edelkamp and Jabbar [14]. The new algorithm exhibits similar I/O complexity with respect to the size of the graph while it avoids quadratic increase in the size of the graph. Therefore, the number of I/O operations performed is significantly lower and the algorithm exhibits better practical performance.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.