|
3122
|
1 |
<!-- $Id$ -->
|
|
|
2 |
<HTML><HEAD><TITLE>HOL/Induct/README</TITLE></HEAD><BODY>
|
|
|
3 |
|
|
|
4 |
<H2>Induct--Examples of (Co)Inductive Definitions</H2>
|
|
|
5 |
|
|
|
6 |
<P>This directory is a collection of small examples to demonstrate
|
|
|
7 |
Isabelle/HOL's (co)inductive definitions package. Large examples appear on
|
|
|
8 |
many other directories, such as Auth, IMP and Lambda.
|
|
|
9 |
|
|
|
10 |
<UL>
|
|
|
11 |
<LI><KBD>Perm</KBD> is a simple theory of permutations of lists.
|
|
|
12 |
|
|
5417
|
13 |
<LI><KBD>FoldSet</KBD> declares a <EM>fold</EM> functional for finite sets.
|
|
|
14 |
Let f be an associative-commutative function with identity e.
|
|
|
15 |
For n non-negative we have
|
|
|
16 |
<PRE>
|
|
|
17 |
fold f e {x1,...,xn} = f x1 (... (f xn e))
|
|
|
18 |
</PRE>
|
|
|
19 |
|
|
3122
|
20 |
<LI><KBD>Comb</KBD> proves the Church-Rosser theorem for combinators (<A
|
|
|
21 |
HREF="http://www.cl.cam.ac.uk/ftp/papers/reports/TR396-lcp-generic-automatic-proof-tools.ps.gz">paper
|
|
|
22 |
available</A>).
|
|
|
23 |
|
|
|
24 |
<LI><KBD>Mutil</KBD> is the famous Mutilated Chess Board problem (<A
|
|
|
25 |
HREF="http://www.cl.cam.ac.uk/ftp/papers/reports/TR394-lcp-mutilated-chess-board.dvi.gz">paper
|
|
|
26 |
available</A>).
|
|
|
27 |
|
|
|
28 |
<LI><KBD>PropLog</KBD> proves the completeness of a formalization of
|
|
|
29 |
propositional logic (<A
|
|
|
30 |
HREF="http://www.cl.cam.ac.uk/Research/Reports/TR312-lcp-set-II.ps.gz">paper
|
|
|
31 |
available</A>).
|
|
|
32 |
|
|
|
33 |
<LI><KBD>LFilter</KBD> is an inductive/corecursive formalization of the
|
|
|
34 |
<EM>filter</EM> functional for infinite streams.
|
|
|
35 |
|
|
|
36 |
<LI><KBD>Exp</KBD> demonstrates the use of iterated inductive definitions to
|
|
|
37 |
reason about mutually recursive relations.
|
|
|
38 |
</UL>
|
|
|
39 |
|
|
|
40 |
<HR>
|
|
|
41 |
<P>Last modified 7 May 1997
|
|
|
42 |
|
|
|
43 |
<ADDRESS>
|
|
|
44 |
<A NAME="lcp@cl.cam.ac.uk" HREF="mailto:lcp@cl.cam.ac.uk">lcp@cl.cam.ac.uk</A>
|
|
|
45 |
</ADDRESS>
|
|
|
46 |
</BODY></HTML>
|