Detail publikace

Fast Acceleration of Ultimately Periodic Relations

BOZGA, M.; IOSIF, R.; KONEČNÝ, F. Fast Acceleration of Ultimately Periodic Relations. TR-2010-3, Grenoble: VERIMAG, 2010. p. 0-0.
Název česky
Akcelerace periodických relací
Typ
zpráva odborná
Jazyk
anglicky
Autoři
Bozga Marius
Radu Iosif
Konečný Filip, Ing., Ph.D.
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
BibTeX 
@techreport{BUT192711,
  author="Marius {Bozga} and Iosif {Radu} and Filip {Konečný}",
  title="Fast Acceleration of Ultimately Periodic Relations",
  year="2010",
  publisher="VERIMAG",
  address="TR-2010-3, Grenoble",
  pages="24",
  url="http://www-verimag.imag.fr/TR/TR-2010-3.pdf"
}
Nahoru