equal
deleted
inserted
replaced
42 \end{isamarkuptext}% |
42 \end{isamarkuptext}% |
43 {\isachardoublequote}mc{\isacharparenleft}AF\ f{\isacharparenright}\ \ \ \ {\isacharequal}\ lfp{\isacharparenleft}af{\isacharparenleft}mc\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}% |
43 {\isachardoublequote}mc{\isacharparenleft}AF\ f{\isacharparenright}\ \ \ \ {\isacharequal}\ lfp{\isacharparenleft}af{\isacharparenleft}mc\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}% |
44 \begin{isamarkuptext}% |
44 \begin{isamarkuptext}% |
45 \noindent |
45 \noindent |
46 Because \isa{af} is monotone in its second argument (and also its first, but |
46 Because \isa{af} is monotone in its second argument (and also its first, but |
47 that is irrelevant) \isa{af\ A} has a least fixpoint:% |
47 that is irrelevant) \isa{af\ A} has a least fixed point:% |
48 \end{isamarkuptext}% |
48 \end{isamarkuptext}% |
49 \isacommand{lemma}\ mono{\isacharunderscore}af{\isacharcolon}\ {\isachardoublequote}mono{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}\isanewline |
49 \isacommand{lemma}\ mono{\isacharunderscore}af{\isacharcolon}\ {\isachardoublequote}mono{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}\isanewline |
50 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ mono{\isacharunderscore}def\ af{\isacharunderscore}def{\isacharparenright}\isanewline |
50 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ mono{\isacharunderscore}def\ af{\isacharunderscore}def{\isacharparenright}\isanewline |
51 \isacommand{apply}\ blast\isanewline |
51 \isacommand{apply}\ blast\isanewline |
52 \isacommand{done}% |
52 \isacommand{done}% |
58 \isacommand{theorem}\ AF{\isacharunderscore}lemma{\isadigit{1}}{\isacharcolon}\isanewline |
58 \isacommand{theorem}\ AF{\isacharunderscore}lemma{\isadigit{1}}{\isacharcolon}\isanewline |
59 \ \ {\isachardoublequote}lfp{\isacharparenleft}af\ A{\isacharparenright}\ {\isasymsubseteq}\ {\isacharbraceleft}s{\isachardot}\ {\isasymforall}\ p\ {\isasymin}\ Paths\ s{\isachardot}\ {\isasymexists}\ i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharbraceright}{\isachardoublequote}% |
59 \ \ {\isachardoublequote}lfp{\isacharparenleft}af\ A{\isacharparenright}\ {\isasymsubseteq}\ {\isacharbraceleft}s{\isachardot}\ {\isasymforall}\ p\ {\isasymin}\ Paths\ s{\isachardot}\ {\isasymexists}\ i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharbraceright}{\isachardoublequote}% |
60 \begin{isamarkuptxt}% |
60 \begin{isamarkuptxt}% |
61 \noindent |
61 \noindent |
62 In contrast to the analogous property for \isa{EF}, and just |
62 In contrast to the analogous property for \isa{EF}, and just |
63 for a change, we do not use fixpoint induction but a weaker theorem, |
63 for a change, we do not use fixed point induction but a weaker theorem, |
64 \isa{lfp{\isacharunderscore}lowerbound}: |
64 \isa{lfp{\isacharunderscore}lowerbound}: |
65 \begin{isabelle}% |
65 \begin{isabelle}% |
66 \ \ \ \ \ f\ S\ {\isasymsubseteq}\ S\ {\isasymLongrightarrow}\ lfp\ f\ {\isasymsubseteq}\ S% |
66 \ \ \ \ \ f\ S\ {\isasymsubseteq}\ S\ {\isasymLongrightarrow}\ lfp\ f\ {\isasymsubseteq}\ S% |
67 \end{isabelle} |
67 \end{isabelle} |
68 The instance of the premise \isa{f\ S\ {\isasymsubseteq}\ S} is proved pointwise, |
68 The instance of the premise \isa{f\ S\ {\isasymsubseteq}\ S} is proved pointwise, |
308 Let us close this section with a few words about the executability of our model checkers. |
308 Let us close this section with a few words about the executability of our model checkers. |
309 It is clear that if all sets are finite, they can be represented as lists and the usual |
309 It is clear that if all sets are finite, they can be represented as lists and the usual |
310 set operations are easily implemented. Only \isa{lfp} requires a little thought. |
310 set operations are easily implemented. Only \isa{lfp} requires a little thought. |
311 Fortunately the HOL library proves that in the case of finite sets and a monotone \isa{F}, |
311 Fortunately the HOL library proves that in the case of finite sets and a monotone \isa{F}, |
312 \isa{lfp\ F} can be computed by iterated application of \isa{F} to \isa{{\isacharbraceleft}{\isacharbraceright}} until |
312 \isa{lfp\ F} can be computed by iterated application of \isa{F} to \isa{{\isacharbraceleft}{\isacharbraceright}} until |
313 a fixpoint is reached. It is actually possible to generate executable functional programs |
313 a fixed point is reached. It is actually possible to generate executable functional programs |
314 from HOL definitions, but that is beyond the scope of the tutorial.% |
314 from HOL definitions, but that is beyond the scope of the tutorial.% |
315 \end{isamarkuptext}% |
315 \end{isamarkuptext}% |
316 \end{isabellebody}% |
316 \end{isabellebody}% |
317 %%% Local Variables: |
317 %%% Local Variables: |
318 %%% mode: latex |
318 %%% mode: latex |