Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I was reading a paper A Generic Cyclic Theorem Prover. This paper explains about automated theorem prover based on various instantiations like the notion of first order logic equations with inductive definitions using cyclic proofs. I was unable to understand about why cyclic proofs are required. As far as I understand, sometime with the induction rules, we can go to an infinite loop, to avoid this condition of going into infinite loop, they introduced cyclic proofs. Can anyone please correct me if I am wrong?

share|cite|improve this question
It would be nice if you can explain what is a cyclic proof for those of us who are not familiar with the topic so we can also understand the question. :) –  Kaveh Jan 14 '13 at 4:17
Very briefly, I think the point is that you discover the induction principle that is good to use while searching for the proof, rather than first selecting an induction principle and then trying to see if you can build a proof. Suppose you want to prove that the sum of two even numbers is even. You could use induction on natural numbers, or you could use induction on even numbers, as done here: Coq'Art, section 8.3.3 The alternative is to discover which induction works. But, let's see if the authors correct me. ;) –  Radu GRIGore Jan 14 '13 at 21:50

1 Answer 1

up vote 8 down vote accepted

In order to reason about inductively defined objects (numbers, lists, trees...), one needs to use induction, or some principle that is at least as powerful as induction.

But explicit induction rules cause huge difficulties for automatic proof search, because they typically force you to invent the necessary induction schema and induction hypotheses at the beginning of the proof. For some discussion of these difficulties, see this paper by Bundy.

Cyclic proof is an alternative to explicit induction; that is, instead of using a standard proof system with explicit induction rules, one can use a cyclic proof system without explicit induction rules. This allows a somewhat more exploratory approach to proof search, where the induction argument is essentially created implicitly through the discovery of a cyclic proof. See this paper for a comparison between cyclic and non-cyclic proofs (for first-order logic with inductive predicates).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.