[Agda] Termination proof in partiality monad
Shin-Cheng Mu
scm at iis.sinica.edu.tw
Tue Nov 18 16:23:47 CET 2008
On Nov 17, 2008, at 1:47 PM, Edsko de Vries wrote:
> Now I have a simple question: given an inductive characterization of
> termination, how would one prove that fac terminates? I have tried
> various approaches (in Coq) but am making no progress at all.
I hope my previous experiments are relevant:
http://www.iis.sinica.edu.tw/~scm/2008/general-recursion-using-coindutive-monad/
http://www.iis.sinica.edu.tw/~scm/2008/general-recursion-using-coinductive-monad-got-right/
These are basically Adam Megacz's work (in Coq) ported to Agda:
http://portal.acm.org/citation.cfm?id=1292597.1292601
Megacz's monad, on the other hand, is an extension of Venanzio
Capretta's approach, which is probably closer to Dan Doel's
monad.
It should be even easier to prove the termination of
factorial, since we only need an induction (rather than
strong induction) to prove that fact n converges for
all n.
sincerely,
Shin
More information about the Agda
mailing list