Rewriting, Inference, and Proof


Shankar, N. (2010). Rewriting, Inference, and Proof. In: Ölveczky, P.C. (eds) Rewriting Logic and Its Applications. WRLA 2010. Lecture Notes in Computer Science, vol 6381. Springer, Berlin, Heidelberg.


Rewriting is a form of inference, and one that interacts in several ways with other forms of inference such as decision procedures and proof search. We discuss a range of issues at the intersection of rewriting and inference. How can other inference procedures be combined with rewriting? Can rewriting be used to describe inference procedures? What are some of the theoretical challenges and practical applications of combining rewriting and inference? How can rewriters, decision procedures, and their combination be certified? We discuss these problems in the context of our ongoing effort to use PVS as a metatheoretic framework to construct a proof kernel for justifying the claims of theorem provers, rewriters, model checkers, and satisfiability solvers.

Keywords: Inference System, Decision Procedure, Predicate Symbol, Proof Obligation, Inference Procedure

Read more from SRI