کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949453 1364241 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Horn clause verification with convex polyhedral abstraction and tree automata-based refinement
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Horn clause verification with convex polyhedral abstraction and tree automata-based refinement
چکیده انگلیسی


- We construct a correspondence between Horn clauses and finite tree automata (FTA).
- We construct a refined clauses from an FTA of the clauses and an infeasible trace.
- We propose a splitting operator on FTAs and describe its role in verification.
- We demonstrate the feasibility of our approach in practice.

In this paper we apply tree-automata techniques to refinement of abstract interpretation in Horn clause verification. We go beyond previous work on refining trace abstractions; firstly we handle tree automata rather than string automata and thereby can capture traces in any Horn clause derivations rather than just transition systems; secondly, we show how algorithms manipulating tree automata interact with abstract interpretations, establishing progress in refinement and generating refined clauses that eliminate causes of imprecision. We show how to derive a refined set of Horn clauses in which given infeasible traces have been eliminated, using a recent optimised algorithm for tree automata determinisation. We also show how we can introduce disjunctive abstractions selectively by splitting states in the tree automaton. The approach is independent of the abstract domain and constraint theory underlying the Horn clauses. Experiments using linear constraint problems and the abstract domain of convex polyhedra show that the refinement technique is practical and that iteration of abstract interpretation with tree automata-based refinement solves many challenging Horn clause verification problems. We compare the results with other state-of-the-art Horn clause verification tools.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Languages, Systems & Structures - Volume 47, Part 1, January 2017, Pages 2-18
نویسندگان
, ,