I/O Efficient Accepting Cycle Detection

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00019426" target="_blank" >RIV/00216224:14330/07:00019426 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
I/O Efficient Accepting Cycle Detection
Original language 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.
Czech name
I/O Efektivní detekce akceptujícího cyklu
Czech description
Výsledkem je adaptace existujícího algoritmu OWCTY pro detekci akceptujících cyklů bez použití DFS na I/O efektivni verzi a porovnání I/O efektivity s existujícím algoritmem pro daný problém publikovaný Edelkampem a Jabbarem v [14]. Nově navržený algoritmus vykazuje podobnou I/O složitost vzhledem k velikosti grafu, ale vyhýbá se kvadratickému nárůstu prohledáváného grafu, která je přítomna v algoritmu Edelkampa a Jabbara a je vynucena technikou převedení detekce cyklů na testování relace dosažitelnosti. Ve skutečnosti tedy nový algoritmus provádí výrazně menší počet I/O operací.

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
19th International Conference on Computer Aided Verification
ISBN
978-3-540-73367-6
ISSN
—
e-ISSN
—
Number of pages
13
Pages from-to
281-293
Publisher name
Springer
Place of publication
Berlin, Heidelberg
Event location
Berlin, Heidelberg
Event date
Jan 1, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)