Skip to main content

TS

Model evolution with equality modulo built-in theories

Authors

Peter Baumgartner and Cesare Tinelli

NICTA

Australian National University

The University of Iowa
USA

Abstract

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

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

Download

Served by Apache on Linux on seL4.