Department of Intelligent Systems

Technical report

HRUŠKA Martin, HOLÍK Lukáš, LENGÁL Ondřej, ROGALEWICZ Adam and VOJNAR Tomáš. Counterexample Validation and Interpolation-Based Refinement for Forest Automata. Brno: Faculty of Information Technology BUT, 2017.
Publication language:english
Original title:Counterexample Validation and Interpolation-Based Refinement for Forest Automata
Title (cs):Ověřování protipříkladů a zjemňovaní abstrakce založené na interpolantech pro lesní automaty
Pages:1-23
Place:Brno, CZ
Year:2017
Publisher:Faculty of Information Technology BUT
Keywords
program analysis, shape analysis, counterexample validation, abstraction refinement, forest automata, tree automata
Annotation
In the context of shape analysis, counterexample validation and abstraction refinement are complex and so far not sufficiently resolved problems. We provide a novel solution to both of these problems in the context of fully automated and rather general shape analysis based on forest automata. Our approach is based on backward symbolic execution on forest automata, allowing one to derive automata-based interpolants and refine the automata abstraction used. The approach allows one to distinguish true and spurious counterexamples and guarantees progress of the abstraction refinement. We have implemented the approach in the FORESTER tool and present promising experimental results.
http://www.fit.vutbr.cz/~lengal/pub/FIT-TR-2016-03.pdf
BibTeX:
@TECHREPORT{
   author = {Martin Hru{\v{s}}ka and Luk{\'{a}}{\v{s}} Hol{\'{i}}k and
	Ond{\v{r}}ej Leng{\'{a}}l and Adam Rogalewicz and
	Tom{\'{a}}{\v{s}} Vojnar},
   title = {Counterexample Validation and Interpolation-Based Refinement
	for Forest Automata},
   pages = {1--23},
   year = {2017},
   location = {Brno, CZ},
   publisher = {Faculty of Information Technology BUT},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso-8859-2?id=11342}
}

Your IPv4 address: 54.198.104.202
Switch to IPv6 connection

DNSSEC [dnssec]