Decomposition by tree dimension in Horn clause verification

Bishoksan Kafle, John Patrick Gallagher, Pierre Ganty

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In this paper we investigate the use of the concept of tree dimension in Horn clause analysis and verification. The dimension of a tree is a measure of its non-linearity - for example a list of any length has dimension zero while a complete binary tree has dimension equal to its height. We apply this concept to trees corresponding to Horn clause derivations. A given set of Horn clauses P can be transformed into a new set of clauses P=<k, whose derivation trees are the subset of P's derivation trees with dimension at most k. Similarly, a set of clauses P>k can be obtained from P whose derivation trees have dimension at least k + 1. In order to prove some property of all derivations of P, we systematically apply these transformations, for various values of k, to decompose the proof into separate proofs for P=<k and P>k (which could be executed in parallel). We show some preliminary results indicating that decomposition by tree dimension is a potentially useful proof technique. We also investigate the use of existing automatic proof tools to prove some interesting properties about dimension(s) of feasible derivation trees of a given program.
Original languageEnglish
Title of host publicationProceedings of the Third International Workshop on Verification and Program Transformation
EditorsAlexei Lisitsa, Andrei P. Nemytykh, Alberto Pettorossi
Number of pages14
Place of PublicationLondon
Publication date7 Dec 2015
Commissioning bodyIMDEA Software Institute
Publication statusPublished - 7 Dec 2015
EventThird International Workshop on Verification and Program Transformation - London, United Kingdom
Duration: 11 Apr 2015 → …


WorkshopThird International Workshop on Verification and Program Transformation
Country/TerritoryUnited Kingdom
Period11/04/2015 → …
Internet address
SeriesElectronic Proceedings in Theoretical Computer Science


  • Tree dimension
  • proof decomposition
  • program transformation
  • Horn clauses

Cite this