Publication details

<< back
 

I/O Efficient Accepting Cycle Detection

Basic information
Original title:I/O Efficient Accepting Cycle Detection
Authors:Jiří Barnat, Luboš Brim, Pavel Šimeček
Further information
Citation:BARNAT, Jiří - BRIM, Luboš - ŠIMEČEK, Pavel. I/O Efficient Accepting Cycle Detection. In 19th International Conference on Computer Aided Verification. Berlin, Heidelberg : Springer, 2007. ISBN 978-3-540-73367-6, pp. 281-293.
Original language:English
Field:Informatika
Type:Article in Proceedings
Keywords:I/O efficient; accepting cycle detection

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:

 
 
top