Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T17:36:21.879Z Has data issue: false hasContentIssue false

Tree dimension in verification of constrained Horn clauses

Published online by Cambridge University Press:  11 May 2018

BISHOKSAN KAFLE
Affiliation:
School of Computing and Information Systems, The University of Melbourne, Melbourne, Victoria, Australia (e-mail: bishoksank@unimelb.edu.au)
JOHN P. GALLAGHER
Affiliation:
Department of People and Technology, Roskilde University, Roskilde, Denmark, and IMDEA Software Institute, Pozuelo de Alarcón, Madrid, Spain, IMDEA Software Institute (e-mail: jpg@ruc.dk)
PIERRE GANTY
Affiliation:
IMDEA Software Institute, Pozuelo de Alarcón, Madrid, Spain (e-mail: pierre.ganty@imdea.org)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper, we show how the notion of tree dimension can be used in the verification of constrained Horn clauses (CHCs). The dimension of a tree is a numerical measure of its branching complexity and the concept here applies to Horn clause derivation trees. Derivation trees of dimension zero correspond to derivations using linear CHCs, while trees of higher dimension arise from derivations using non-linear CHCs. We show how to instrument CHCs predicates with an extra argument for the dimension, allowing a CHC verifier to reason about bounds on the dimension of derivations. Given a set of CHCs P, we define a transformation of P yielding a dimension-bounded set of CHCs P≤k. The set of derivations for P≤k consists of the derivations for P that have dimension at most k. We also show how to construct a set of clauses denoted P>k whose derivations have dimension exceeding k. We then present algorithms using these constructions to decompose a CHC verification problem. One variation of this decomposition considers derivations of successively increasing dimension. The paper includes descriptions of implementations and experimental results.

Information

Type
Original Article
Copyright
Copyright © Cambridge University Press 2018