  This paper investigates the combination of abstract interpretation over the
domain of convex polyhedra with interpolant tree automata, in an
abstraction-refinement scheme for Horn clause verification. These techniques
have been previously applied separately, but are combined in a new way in this
paper. The role of an interpolant tree automaton is to provide a generalisation
of a spurious counterexample during refinement, capturing a possibly infinite
set of spurious counterexample traces. In our approach these traces are then
eliminated using a transformation of the Horn clauses. We compare this approach
with two other methods; one of them uses interpolant tree automata in an
algorithm for trace abstraction and refinement, while the other uses abstract
interpretation over the domain of convex polyhedra without the generalisation
step. Evaluation of the results of experiments on a number of Horn clause
verification problems indicates that the combination of interpolant tree
automaton with abstract interpretation gives some increase in the power of the
verification tool, while sometimes incurring a performance overhead.
