src/HOL/Hoare_Parallel/document/root.tex
author haftmann
Thu, 19 Jun 2025 17:15:40 +0200
changeset 82734 89347c0cc6a3
parent 73595 aece5cc9efb7
permissions -rw-r--r--
treat map_filter similar to list_all, list_ex, list_ex1
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
13106
f6561b003a35 \documentclass{report};
wenzelm
parents: 13099
diff changeset
     1
\documentclass[11pt,a4paper]{report}
73595
aece5cc9efb7 simplified typesetting of \<guillemotleft>...\<guillemotright>;
wenzelm
parents: 58884
diff changeset
     2
\usepackage[T1]{fontenc}
13033
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
     3
\usepackage{graphicx}
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
     4
\usepackage{isabelle,isabellesym}
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
     5
\usepackage{pdfsetup}
13021
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
     6
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
     7
\urlstyle{rm}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
     8
\isabellestyle{it}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
     9
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    10
\begin{document}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    11
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    12
\title{Hoare Logic for Parallel Programs}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    13
\author{Leonor Prensa Nieto}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    14
\maketitle
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    15
13099
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    16
\begin{abstract}\noindent
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    17
  In the following theories a formalization of the Owicki-Gries and
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    18
  the rely-guarantee methods is presented. These methods are widely
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    19
  used for correctness proofs of parallel imperative programs with
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    20
  shared variables.  We define syntax, semantics and proof rules in
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    21
  Isabelle/HOL.  The proof rules also provide for programs
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    22
  parameterized in the number of parallel components. Their
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    23
  correctness w.r.t.\ the semantics is proven.  Completeness proofs
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    24
  for both methods are extended to the new case of parameterized
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    25
  programs. (These proofs have not been formalized in Isabelle. They
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    26
  can be found in~\cite{Prensa-PhD}.)  Using this formalizations we
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    27
  verify several non-trivial examples for parameterized and
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    28
  non-parameterized programs.  For the automatic generation of
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    29
  verification conditions with the Owicki-Gries method we define a
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    30
  tactic based on the proof rules.  The most involved examples are the
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    31
  verification of two garbage-collection algorithms, the second one
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    32
  parameterized in the number of mutators.
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    33
19401
259e2bbba43c added references
nipkow
parents: 13106
diff changeset
    34
For excellent descriptions of this work see
259e2bbba43c added references
nipkow
parents: 13106
diff changeset
    35
\cite{NipkowP-FASE99,PrenEsp00,Prensa-PhD,Prensa-ESOP03}.
259e2bbba43c added references
nipkow
parents: 13106
diff changeset
    36
13099
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    37
\end{abstract}
4bb592cdde0e added abstract;corrected RG_Basic Hoare rule.
prensani
parents: 13036
diff changeset
    38
13021
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    39
\pagestyle{plain}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    40
\thispagestyle{empty}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    41
\tableofcontents
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    42
13036
wenzelm
parents: 13033
diff changeset
    43
\clearpage
wenzelm
parents: 13033
diff changeset
    44
13033
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    45
\begin{center}
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    46
  \includegraphics[scale=0.7]{session_graph}  
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    47
\end{center}
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    48
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    49
\newpage
d6a09050a40d added session_graph;
wenzelm
parents: 13021
diff changeset
    50
13021
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    51
\parindent 0pt\parskip 0.5ex
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    52
\input{session}
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    53
19401
259e2bbba43c added references
nipkow
parents: 13106
diff changeset
    54
\bibliographystyle{plain}
259e2bbba43c added references
nipkow
parents: 13106
diff changeset
    55
\bibliography{root}
13021
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    56
cd0075346431 Adding root.tex for HoareParallel
prensani
parents:
diff changeset
    57
\end{document}