Trustworthy Systems

Model evolution with equality modulo built-in theories


Peter Baumgartner and Cesare Tinelli


Australian National University

The University of Iowa


Many applications of automated deduction require reasoning modulo background theories, in particular some form of integer arithmetic. Developing corresponding automated reasoning systems that are also able to deal with quantified formulas has recently been an active area of research. We contribute to this line of research and propose a novel instantiation-based method for a large fragment of first-order logic with equality modulo a given complete background theory, such as linear integer arithmetic. The new calculus is an extension of the Model Evolution Calculus with Equality, a first-order logic version of the propositional DPLL procedure, including its ordering-based redundancy criteria. We present a basic version of the calculus and prove it sound and (refutationally) complete under certain conditions.

BibTeX Entry

    isbn             = {978-3-642-22437-9},
    publisher        = {Springer},
    booktitle        = {International Conference on Automated Deduction},
    month            = apr,
    paperurl         = {},
    year             = {2011},
    editor           = {{Nikolaj Bjoerner and Viorica Sofronie-Stokkermans }},
    keywords         = {automated reasoning, satisfiability modulo theories},
    title            = {Model Evolution with Equality Modulo Built-in Theories},
    pages            = {85--100},
    author           = {Baumgartner, Peter and Tinelli, Cesare},
    address          = {Wroclaw, Poland}