Browse/search for people

Publication - Dr Steven Ramsay

    Higher-order constrained horn clauses for verification

    Citation

    Burn, TC, Ong, L & Ramsay, S, 2018, ‘Higher-order constrained horn clauses for verification’. Proceedings of the ACM on Programming Languages, vol 2.

    Abstract

    Motivated by applications in automated verification of higher-order functional programs, we develop a notion of constrained Horn clauses in higher-order logic and a decision problem concerning their satisfiability. We show that, although satisfiable systems of higher-order clauses do not generally have least models, there is a notion of canonical model obtained through a reduction to a problem concerning a kind of monotone logic program. Following work in higher-order program verification, we develop a refinement type system in order to reason about and automate the search for models. This provides a sound but incomplete method for solving the decision problem. Finally, we show that there is a sense in which we can use refinement types to express properties of terms whilst staying within the higher-order constrained Horn clause framework.

    Full details in the University publications repository