Detail publikace
Fast Acceleration of Ultimately Periodic Relations
BOZGA Marius, IOSIF Radu a KONEČNÝ Filip. Fast Acceleration of Ultimately Periodic Relations. In: Computer Aided Verification. Lecture Notes in Computer Science, roč. 6174. Berlin: Springer Verlag, 2010, s. 227-242. ISBN 978-3-642-14294-9.
Název česky
Akcelerace periodických relací
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
URL
Klíčová slova
akcelerace, systémy s čítači, relace diferenčních mezí, oktagonální relace, afinní relace konečných monoidů
Abstrakt
Výpočet tranzitivních uzávěrů relací nad celými čísly je klíčem pro nalezení přesných invariantů programů s celočíselnými proměnnými. Tento článek popisuje efektivní algoritmus pro výpočet tranzitivního uzávěru pro tyto třídy relací: relace diferenčních mezí, oktagonální relace, a afinní relace konečných monoidů. Z teoretického hlediska práce přináší sjednocující řešení problému akcelerace pro tyto tři třídy. Z praktického hlediska nová metoda přináší zrychlení až o čtyři řády oproti předchozí metodě a je tudíž slibným přístupem pro verifikaci programů s celočíselnými proměnnými.
Rok
2010
Strany
227-242
Sborník
Computer Aided Verification
Řada
Lecture Notes in Computer Science
Svazek
6174
Konference
22nd International Conference on Computer-Aided Verification, Edinburgh, GB
ISBN
978-3-642-14294-9
Vydavatel
Springer Verlag
Místo
Berlin, DE
BibTeX
@INPROCEEDINGS{FITPUB9278, author = "Marius Bozga and Radu Iosif and Filip Kone\v{c}n\'{y}", title = "Fast Acceleration of Ultimately Periodic Relations", pages = "227--242", booktitle = "Computer Aided Verification", series = "Lecture Notes in Computer Science", volume = 6174, year = 2010, location = "Berlin, DE", publisher = "Springer Verlag", ISBN = "978-3-642-14294-9", language = "english", url = "https://www.fit.vut.cz/research/publication/9278" }