Paper: Automatic Proofs by Induction in Equational Theories Without Constructors (at LICS 1986)

Authors: Jean-Pierre Jouannaud Emmanuel Kounalis

Abstract

Inductionless Induction consists of using pure equational reasoning for proving validity of an equation in the initial algebra of a set of equational axioms, which would normally require some kind of induction.
A key new concept, inductive reducibility, allows us to extend these techniques in various directions: incomplete specifications, non free constructors, conditional and equational term rewriting systems. In addition, we get for free a simple algorithm to exhibit a set of constructors of a specification. Finally, we modify our algorithm for proving the consistency property of an enrichment of a specification by new operators and new equations.

BibTeX

  @InProceedings{JouannaudKounalis-AutomaticProofsbyIn,
    author = 	 {Jean-Pierre Jouannaud and Emmanuel Kounalis},
    title = 	 {Automatic Proofs by Induction in Equational Theories Without Constructors},
    booktitle =  {Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS 1986)},
    year =	 {1986},
    month =	 {June}, 
    pages =      {358--366},
    location =   {Cambridge, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }