Detail publikace

Fast Acceleration of Ultimately Periodic Relations

BOZGA, M.; IOSIF, R.; KONEČNÝ, F. Fast Acceleration of Ultimately Periodic Relations. Computer Aided Verification. Lecture Notes in Computer Science. Berlin: Springer Verlag, 2010. p. 227-242. ISBN: 978-3-642-14294-9.
Název česky
Akcelerace periodických relací
Typ
článek ve sborníku konference
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
227–242
Sborník
Computer Aided Verification
Řada
Lecture Notes in Computer Science
Svazek
6174
ISBN
978-3-642-14294-9
Vydavatel
Springer Verlag
Místo
Berlin
BibTeX 
@inproceedings{BUT34831,
  author="Marius {Bozga} and Iosif {Radu} and Filip {Konečný}",
  title="Fast Acceleration of Ultimately Periodic Relations",
  booktitle="Computer Aided Verification",
  year="2010",
  series="Lecture Notes in Computer Science",
  volume="6174",
  pages="227--242",
  publisher="Springer Verlag",
  address="Berlin",
  isbn="978-3-642-14294-9",
  url="https://www.fit.vut.cz/research/publication/9278/"
}
Nahoru