Detail publikace

Fast Acceleration of Ultimately Periodic Relations

BOZGA Marius, IOSIF Radu a KONEČNÝ Filip. Fast Acceleration of Ultimately Periodic Relations. TR-2010-3, Grenoble: VERIMAG, 2010.
Název česky
Akcelerace periodických relací
Typ
technická zpráva
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
24
Vydavatel
VERIMAG
Místo
TR-2010-3, Grenoble, FR
BibTeX 
@TECHREPORT{FITPUB9279,
   author = "Marius Bozga and Radu Iosif and Filip Kone\v{c}n\'{y}",
   title = "Fast Acceleration of Ultimately Periodic Relations",
   pages = 24,
   year = 2010,
   location = "TR-2010-3, Grenoble, FR",
   publisher = "VERIMAG",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9279"
}
Nahoru