|
10865
|
1 |
\chapter{Inductively Defined Sets} \label{chap:inductive}
|
|
11428
|
2 |
\index{inductive definitions|(}
|
|
10242
|
3 |
|
|
|
4 |
This chapter is dedicated to the most important definition principle after
|
|
|
5 |
recursive functions and datatypes: inductively defined sets.
|
|
|
6 |
|
|
11147
|
7 |
We start with a simple example: the set of even numbers. A slightly more
|
|
|
8 |
complicated example, the reflexive transitive closure, is the subject of
|
|
|
9 |
{\S}\ref{sec:rtc}. In particular, some standard induction heuristics are
|
|
|
10 |
discussed. Advanced forms of inductive definitions are discussed in
|
|
|
11 |
{\S}\ref{sec:adv-ind-def}. To demonstrate the versatility of inductive
|
|
|
12 |
definitions, the chapter closes with a case study from the realm of
|
|
|
13 |
context-free grammars. The first two sections are required reading for anybody
|
|
|
14 |
interested in mathematical modelling.
|
|
10219
|
15 |
|
|
10884
|
16 |
\input{Inductive/even-example}
|
|
10762
|
17 |
\input{Inductive/document/Mutual}
|
|
10225
|
18 |
\input{Inductive/document/Star}
|
|
10242
|
19 |
|
|
11216
|
20 |
\section{Advanced Inductive Definitions}
|
|
11147
|
21 |
\label{sec:adv-ind-def}
|
|
10884
|
22 |
\input{Inductive/advanced-examples}
|
|
10371
|
23 |
|
|
10520
|
24 |
\input{Inductive/document/AB}
|
|
|
25 |
|
|
11428
|
26 |
\index{inductive definitions|)}
|