doc-src/TutorialI/tricks.tex
author nipkow
Wed, 30 Aug 2000 18:09:20 +0200
changeset 9754 a123a64cadeb
parent 9743 d18d5c4a1f80
child 9933 9feb1e0c4cb3
permissions -rw-r--r--
*** empty log message ***
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9743
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     1
\chapter{The Tricks of the Trade}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     2
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     3
\section{Simplification}
9754
a123a64cadeb *** empty log message ***
nipkow
parents: 9743
diff changeset
     4
\label{sec:simplification-II}
9743
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     5
\index{simplification|(}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     6
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     7
\subsection{Advanced features}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     8
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
     9
\subsubsection{Congruence rules}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    10
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    11
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    12
\subsubsection{Permutative rewrite rules}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    13
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    14
A rewrite rule is \textbf{permutative} if the left-hand side and right-hand
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    15
side are the same up to renaming of variables.  The most common permutative
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    16
rule is commutativity: $x+y = y+x$.  Another example is $(x-y)-z = (x-z)-y$.
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    17
Such rules are problematic because once they apply, they can be used forever.
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    18
The simplifier is aware of this danger and treats permutative rules
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    19
separately. For details see~\cite{isabelle-ref}.
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    20
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    21
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    22
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    23
\subsection{How it works}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    24
\label{sec:SimpHow}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    25
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    26
\subsubsection{Higher-order patterns}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    27
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    28
\subsubsection{Local assumptions}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    29
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    30
\subsubsection{The preprocessor}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    31
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    32
\index{simplification|)}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    33
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    34
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    35
\section{Advanced induction techniques}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    36
\label{sec:advanced-ind}
d18d5c4a1f80 *** empty log message ***
nipkow
parents:
diff changeset
    37
\input{Misc/document/AdvancedInd.tex}