doc-src/TutorialI/Inductive/inductive.tex
author nipkow
Sun Nov 26 10:48:38 2000 +0100 (2000-11-26)
changeset 10520 bb9dfcc87951
parent 10468 87dda999deca
child 10762 cd1a2bee5549
permissions -rw-r--r--
*** empty log message ***
nipkow@10219
     1
\chapter{Inductively Defined Sets}
nipkow@10242
     2
\index{inductive definition|(}
nipkow@10242
     3
\index{*inductive|(}
nipkow@10242
     4
nipkow@10242
     5
This chapter is dedicated to the most important definition principle after
nipkow@10242
     6
recursive functions and datatypes: inductively defined sets.
nipkow@10242
     7
paulson@10327
     8
We start with a simple example: the set of even numbers.
paulson@10327
     9
A slightly more complicated example, the
nipkow@10242
    10
reflexive transitive closure, is the subject of {\S}\ref{sec:rtc}. In particular,
nipkow@10242
    11
some standard induction heuristics are discussed. To demonstrate the
nipkow@10242
    12
versatility of inductive definitions, {\S}\ref{sec:CFG} presents a case study
nipkow@10242
    13
from the realm of context-free grammars. The chapter closes with a discussion
nipkow@10242
    14
of advanced forms of inductive definitions.
nipkow@10219
    15
paulson@10327
    16
\input{Inductive/Even}
nipkow@10225
    17
\input{Inductive/document/Star}
nipkow@10242
    18
paulson@10371
    19
\section{Advanced inductive definitions}
paulson@10468
    20
\input{Inductive/Advanced}
paulson@10371
    21
nipkow@10520
    22
\input{Inductive/document/AB}
nipkow@10520
    23
nipkow@10242
    24
\index{inductive definition|)}
nipkow@10242
    25
\index{*inductive|)}