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
Bozga Marius (VERIMAG)
Iosif Radu (VERIMAG)
Konečný Filip, Ing. (UITS FIT VUT)
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"
}
Nahoru