1 \documentclass[a4paper, pagesize, DIV=calc, smallheadings]{article}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb, amsfonts, verbatim}
7 \usepackage{algorithmic}
11 \usepackage[left=3.9cm, right=3.9cm]{geometry}
12 %\usepackage[T1]{fontenc}
16 \renewcommand{\familydefault}{\sfdefault}
17 \renewenvironment{proof}{{\bfseries Proof.}}{}
18 \newcommand{\M}{\mathcal{M}}
19 \newcommand{\N}{\mathbb{N}_0}
20 \newcommand{\F}{\mathcal{F}}
21 \newcommand{\Prop}{\mathcal{P}}
22 \newcommand{\A}{\mathcal{A}}
23 \newcommand{\X}{\mathcal{X}}
24 \newcommand{\U}{\mathcal{U}}
25 \newcommand{\V}{\mathcal{V}}
26 \newcommand{\dnf}{\mathsf{dnf}}
27 \newcommand{\consq}{\mathsf{consq}}
29 \title{\uppercase{\textbf{\Large{A}\large{lgorithmic} \Large{V}\large{erification of} \Large{R}\large{eactive} \Large{S}\large{ystems}}\\
33 \uppercase{{\small{E}\scriptsize{UGEN} \small{S}\scriptsize{AWIN}}}\thanks{\texttt{sawine@informatik.uni-freiburg.de}}\\
34 \uppercase{{\em \small{U}\scriptsize{NIVERSITY OF} \small{F}\scriptsize{REIBURG}}}\thanks{Computer Science Department, Research Group for Foundations of Artificial Intelligence}\\
35 %{\em \small{C}\scriptsize{omputer} \small{S}\scriptsize{cience} \small{D}\scriptsize{epartment}}\\
36 \uppercase{{\em \small{G}\scriptsize{ERMANY}}}\\
37 %\texttt{\footnotesize{sawine@informatik.uni-freiburg.de}}
39 \date{\textsc{\hfill}}
41 \theoremstyle{definition} %plain, definition, remark, proof, corollary
42 \newtheorem*{def:finite words}{Finite words}
43 \newtheorem*{def:infinite words}{Infinite words}
44 \newtheorem*{def:regular languages}{Regular languages}
45 \newtheorem*{def:regular languages closure}{Regular closure}
46 \newtheorem*{def:omega regular languages}{$\omega$-regular languages}
47 \newtheorem*{def:omega regular languages closure}{$\omega$-regular closure}
48 \newtheorem*{def:buechi automata}{Automata}
49 \newtheorem*{def:automata runs}{Runs}
50 \newtheorem*{def:automata acceptance}{Acceptance}
51 \newtheorem*{def:general automata}{Generalised automata}
52 \newtheorem*{def:general acceptance}{Acceptance}
53 \newtheorem*{def:vocabulary}{Vocabulary}
54 \newtheorem*{def:frames}{Frames}
55 \newtheorem*{def:models}{Models}
56 \newtheorem*{def:satisfiability}{Satisfiability}
57 \newtheorem*{def:fs closure}{Closure}
58 \newtheorem*{def:atoms}{Atoms}
59 \newtheorem*{def:rep function}{Representation function}
60 \newtheorem*{def:next}{Next function}
61 \newtheorem*{def:dnf}{Disjunctive normal form}
62 \newtheorem*{def:positive formulae}{Positive formulae}
63 \newtheorem*{def:consq}{Logical consequences}
64 \newtheorem*{def:partial automata}{Partial automata}
67 \newtheorem{prop:vocabulary sat}{Proposition}[section]
68 \newtheorem{prop:general equiv}{Proposition}[section]
69 \newtheorem{prop:computation set=language}{Proposition}[section]
72 \newtheorem{thm:model language}{Theorem}[section]
73 \newtheorem{cor:mod=model language}{Corollary}[thm:model language]
74 \newtheorem{cor:mod=program language}[cor:mod=model language]{Corollary}
75 \newtheorem{thm:model checking}{Theorem}[section]
76 \newtheorem{lem:dnf}{Lemma}[section]
77 \newtheorem{lem:consq}[lem:dnf]{Lemma}
83 %\renewcommand\abstractname{Abstract}
85 Algorithmic verification is an application of automated temporal reasoning based on automata-theoretic model checking. We use the power of modal logics to specify computational properties. System verification provides a correctness proof for the program design with respect to such properties. The methods used are a composition of automata theory, graph theory and modal logics. This text is an introduction to such automata theoretic constructions and space-efficient on-the-fly verification methods for reactive systems.
86 %Algorithmic verification of reactive systems is based on automata-theoretic model checking. Linear temporal logic accommodates the capability for the characterisation of program specifications. For formulae composed in linear temporal logic, it is possible to construct B\"uchi automata constituting the model space of the specification. The verification of reactive systems is composed of such constructions and intersections of the program and specification automata. This paper provides an introduction to the construction techniques of such automata and space-efficient on-the-fly verification methods for reactive systems.
90 \section{Introduction}
91 The rapid digital evolution of semi-conductor design has changed the way of development in the industry. Exponential growth in processing frequencies has massive implications on the complexity of chip-design. When a considerable portion of the development cycle is dedicated to design validation, an increasingly high effort is invested in the realisation of efficient verification methods.
93 The computer hardware industry has adapted to the rise of complexity by the application of automated design verification. Another natural consequence was the preference of standard, non-specialised hardware solutions accompanied by software realisations of the required functionality. Software systems have penetrated all industries, and increasingly so in high-demand and safety-critical application areas. Software programs e.g. provide high-demand server infrastructures for the internet, control our air traffic and protect our lifes in car accidents. When handling such critical systems, it becomes inevitable to verify the correctness of such software solutions.
95 Compared to hardware design, the highly dynamic properties of software components confront us with another state space explosion. Concurrent system designs increase the complexity of verification by some orders of magnitude; and concurrent applications have started to dominate recent software solutions, because we are closing the physical limits for single-core processor frequencies.
97 Again, the industry is facing a \emph{validation crisis} \cite{ref:automated verification} and formal verification methods are in high demand. Deductive, computer-supported verification techniques are an interesting digression, but may not be applicable in the validation of software systems of high complexity. Theories for algorithmic verification have existed for decades and recent successful applications have demonstrated their practical value.
99 In this text, we provide an introduction to formal verification by means of algorithmic methods. Such an algorithmic approach is the base for automated verification procedures. We will concentrate on the validation of reactive programs, without any loss of the general applicability of the presented methods. Reactive systems are, in contrast to terminating programs, continuous processes. Once initiated, a reactive system persists in an active state, where it reacts to concurrent inputs with appropriate actions. Examples of reactive systems are monitoring processes, schedulers and even whole operating systems.
101 The first three sections define the preliminaries for the automata-theoretic constructions. At first, we provide the notion of reasoning about infinite computational paths within formal language theory. Then we tackle those infinite structures with the help of automata theory, which shall build the framework of the formal verification theory. Next we introduce the reader to modal logics, in particular to linear temporal logic. Linear temporal logic is the language we use to talk about program properties, i.e., the propgram specification language.
103 The fifth section interweaves automata theory and modal logics for the formalisation of the automata constructions, i.e., we construct automata depicting the program design and the specified properties. Based on this constructions, we apply the methods presented in the model checking section. The last section is a short excursion into the practical considerations of automated verification. For a successful application of automated verification, we consider ways of reducing the complexity of the automata-theoretic approach.
105 The formal frame of this text is mostly based on Madhavan Mukund's \cite{ref:ltl&büchi} and Moshe Y. Vardi's \cite{ref:handbook} work. We conclude this paper with a discussion of \cite{ref:ltl&büchi}.
107 \section{$\omega$-regular languages}
108 For the formalisation of non-terminating, reactive systems, we need to get familiar with the concept of infinity. When a system is persistently active, the conceptual model of its input becomes an infinite structure, and likewise the description of its computational path. We want to settle this infinite structures within a formal corset.
110 \begin{def:finite words}
111 Let $\Sigma$ be a non-empty set of symbols, called the alphabet. $\Sigma^*$ is the set of all \emph{finite} words over $\Sigma$. A \emph{finite} word $w \in \Sigma^*$ is a \emph{finite} sequence $(v_0,...,v_{n-1})$ of symbols from alphabet $\Sigma$ with length $n = |w|$. $\varepsilon$ denotes the empty word with length $|\varepsilon| = 0$.
112 \end{def:finite words}
114 \begin{def:regular languages}
115 The class of regular languages is defined recursively over an alphabet $\Sigma$:
118 \item $\emptyset$ is regular
119 \item $\{\varepsilon\}$ is regular
120 \item $\forall_{a \in \Sigma}:\{a\}$ is regular
123 \end{def:regular languages}
125 \begin{def:regular languages closure}
126 Let $L_{R_1}, L_{R_2} \in \Sigma^*$ be regular. The class of regular languages is closed under following operations:
130 \item $L_{R_1} \circ L_{R_2}$
131 \item $L_{R_1} \cup L_{R_2}$
132 \item $L_{R_1} \cap L_{R_2}$
133 \item $\overline{L}_{R_1}$ and therefore $L_{R_1} - L_{R_2}$
136 \end{def:regular languages closure}
138 \begin{def:infinite words}
139 $\Sigma^\omega$ is the set of all \emph{infinite} words over $\Sigma$. An \emph{infinite} word $w \in \Sigma^\omega$ is an \emph{infinite} sequence $(v_0,...,v_\infty)$ with length $\infty$. To address the elements of the infinite sequence $w$, we view the word as a function $w : \N \to \Sigma$ with $w(i) = v_i$; thus $w(i)$ denotes the symbol at sequence position $i$ of word $w$; another notation used for $w(i)$ is $w_i$.
140 \end{def:infinite words}
142 \begin{def:omega regular languages}
143 Set $L$ is an $\omega$-language over alphabet $\Sigma$ iff $L \subseteq \Sigma^\omega$. Let $L_R \subseteq \Sigma^*$ be a non-empty regular finite language and $\varepsilon \notin L_R$. A set $L$ is $\omega$-regular iff $L$ is an $\omega$-language and $L = L_R^\omega$.
144 \end{def:omega regular languages}
146 \begin{def:omega regular languages closure}
147 Let $L_{\omega_1}, L_{\omega_2} \subseteq \Sigma^\omega$ be $\omega$-regular languages. The class of $\omega$-regular languages is closed under following operations:
149 \item $L_R \circ L_{\omega_1}$, but \emph{not} $L_{\omega_1} \circ L_R$
150 \item $L_{\omega_1} \cup L_{\omega_2}$, but only \emph{finitely} many times
152 \end{def:omega regular languages closure}
154 \section{B\"uchi automata}
155 Automata theory is the foundation of state-based modelling of computation. Non-deterministic automata provide an elegant way of describing interleaving systems. B\"uchi automata extend the idea of such automata to comfort the need for computational models on infinite inputs.
157 \begin{def:buechi automata}
158 A non-deterministic B\"uchi automaton is a tuple $\A = (\Sigma, S, S_0, \Delta, F)$, where $\Sigma$ is a finite non-empty \emph{alphabet}, $S$ is a finite non-empty set of \emph{states}, $S_0 \subseteq S$ is the set of \emph{initial states}, $F \subseteq S$ is the set of \emph{accepting states} and $\Delta: S \times \Sigma \times S$ is a \emph{transition relation}. When suitable we will use the arrow notation for the transitions, where $s \xrightarrow{a} s'$ iff $(s, a, s') \in \Delta$.
160 A \emph{deterministic B\"uchi automaton} is a specialisation, where the \emph{transition relation} $\Delta$ is a \emph{transition function} $\delta: S \times \Sigma \to S$ and the set $S_0$ of \emph{initial states} contains only a single state $s_0$.
162 Within this text \emph{automaton} will refer to the non-deterministic B\"uchi automaton, unless otherwise noted.
163 \end{def:buechi automata}
165 With infinite inputs comes a new definition of acceptance. Automata on finite inputs define acceptance by the termination of the computation in an accepting state. This notion needs adjustments, when modelling non-terminating systems. First, we need to define the legal sequence of state transitions of an automaton when reading an infinite input word.
167 \begin{def:automata runs}
168 Let $\A = (\Sigma, S, S_0, \Delta, F)$ be an automaton, a run $\rho$ of $\A$ on an infinite word $w = (a_0,a_1,...)$ over alphabet $\Sigma$ is a sequence $\rho = (s_0,s_1,...)$, where $s_0 \in S_0$ and $(s_i, a_i, s_{i+1}) \in \Delta$, for all $i \geq 0$. Again we may view the run sequence as a function $\rho : \N \to S$, where $\rho(i) = s_i$ denotes the state at the $i^{th}$ sequence position.
169 \end{def:automata runs}
171 \begin{def:automata acceptance}
172 Let $\A = (\Sigma, S, S_0, \Delta, F)$ be an automaton and let $\rho$ be a run of $\A$, we define $inf(\rho) = \{s \in S \mid \exists^\omega{n \in \N}: \rho(n) = s\}$, where $\exists^\omega$ denotes the existential quantifier for infinitely many occurances, i.e., $s$ occurs infinitely often in $\rho$.
174 The run $\rho$ is \emph{accepting} iff $inf(\rho) \cap F \neq \emptyset$, i.e., there exists an \emph{accepting state} which occurs infinitely often in the run $\rho$. The automaton $\A$ \emph{accepts} an input word $w$, iff there exists a run $\rho$ of $\A$ on $w$, such that $\rho$ is \emph{accepting}.
176 The language $L_\omega(\A)$ recognised by automaton $\A$ is the set of all infinite words accepted by $\A$. A language $L$ is \emph{B\"uchi-recognisable} iff there is an automaton $\A$ with $L = L_\omega(\A)$. The class of B\"uchi-recognisable languages corresponds to the class of $\omega$-regular languages.
177 \end{def:automata acceptance}
179 Given all legal computations of an automaton, we have defined the acceptance condition. A computation is accepting, if it passes through an accepting state infinitely times. Since the set of states $S$ is finite, there must be a state $s \in S$, which occurs infinitely often within an infinite run; but it is not necessary, that $s$ is an accepting state; notice that $F$ can be an empty set.
181 \subsection{Generalised B\"uchi automata}
182 In the following two sections, we will introduce the modal logic used for the specification of system properties and automata construction on such specifications. To provide a more convenient link between linear temporal logic and B\"uchi automata, we introduce a slightly different formalisation of automata with an extended acceptance condition.
184 \begin{def:general automata}
185 A \emph{generalised B\"uchi automaton} is a tuple $\A = (\Sigma, S, S_0, \Delta, \{F_i\}_{i < k})$ for $i \in \N$, where the \emph{acceppting states} $F_i$ are composed within a finite set with $F_i \subseteq S$.
186 \end{def:general automata}
188 \begin{def:general acceptance}
189 The acceptance condition is adjusted accordingly. A run $\rho$ of $\A$ is \emph{accepting} iff $\forall{i < k}: inf(\rho) \cap F_i \neq \emptyset$.
190 \end{def:general acceptance}
192 \begin{prop:general equiv}
193 Let $\A = (\Sigma, S, S_0, \Delta, \{F_i\}_{i < k})$ be a \emph{generalised automaton} and let $\A_i = (\Sigma, S, S_0, \Delta, F_i)$ be \emph{non-deterministic automata}, then following equivalance condition holds:
194 \[L_\omega(\A) = \bigcap_{i < k} L_\omega(\A_i)\]
195 \end{prop:general equiv}
196 \noindent The equivalance of the language recognition abilities of general and non-deterministic B\"uchi automata follows intuitively.
198 \section{Linear temporal logic}
199 Nothing escapes time, but time has successfully escaped its formalisation in computer science until the rise of the modal logics in the second half of the 20th century \cite{ref:handbook}. All arts and sciences interpret time in some way; where historians prefer the past tense, do science-fiction novels live in the future. Physics knows many time arrows, one of which constitutes the thermodynamic arrow of time, which happens to be the one we perceive by remembering the past and not the future. We compensate our inability to control the direction of time, by the use of rigorous language constructs when reasoning about temporal events.
201 When natural language fails in providing unambiguousness, we have to resort to formal languages. To handle discrete time, we use \emph{propositional logic} as the base and extend it by some more or less modal connectives. There are two major temporal logics used in the specification of system properties, \emph{linear temporal logic (LTL)} and \emph{branching temporal logic (CTL - for Computation Tree Logic)}. Temporal logics are interpreted over computation paths; in LTL such a path depicts a linear sequence, where in CTL the path is a tree, with branching connectives. Throughout this text, we will restrict our attention to LTL.
204 Let $\Prop$ be the countable set of \emph{atomic propositions}. The \emph{alphabet} of the language $L_{LTL}(\Prop)$ is $\Prop \cup \{\neg, \lor, \X, \U\}$. We define the $L_{LTL}(\Prop)$-\emph{formulae} $\varphi$ using following productions:
205 \[\varphi ::= p \in \Prop \,|\, \neg \varphi \,|\, \varphi \lor \varphi \,|\, \X \varphi \,|\, \varphi \U \varphi\]
207 \subsection{Interpretation}
208 The intuition should go as follows: $\neg$ and $\lor$ correspond to the Boolean \emph{negation} and \emph{disjunction}, the unary temporal operator $\X$ reads as \emph{next} and the binary temporal operator $\U$ reads as \emph{until}.
210 LTL is interpreted over \emph{computation paths}, where a computation corresponds to a model over a \emph{Kripke-frame} constructed by the order of natural numbers.
212 \subsection{Semantics}
214 An LTL-\emph{frame} is a tuple $\F = (S, R)$, where $S = \{s_i \mid i \in \N\}$ is the set of states and $R = \{(s_i, s_{i+1}) \mid i \in \N\}$ the set of accessibility relations. Hence $S$ is an isomorphism of $\N$ and $R$ an isomorphism of the strict linear order $(\N, <)$, which corresponds to the linear progression of discrete time.
218 An LTL-\emph{model} is a tuple $\M = (\F, V)$, where $\F$ is a \emph{frame} and $V: S \to 2^\Prop$ a \emph{valuation function}. Intuitively we say $p \in \Prop$ is \emph{true} at time instant $i$ iff $p \in V(i)$.
219 %A \emph{model} is a function $\M: \N \to 2^\Prop$ over \emph{frame} $\F$. The frame constitutes a linear order over $\N$, which corresponds to the linear progression of time from the \emph{present/past} into the \emph{future}. Therefore $\M(i)$ assigns a set of \emph{positive atomic propositions} to each state of time instant $i$. Intuitively we say $p \in \Prop$ is \emph{true} at time instant $i$ iff $p \in \M(i)$.
222 \begin{def:satisfiability}
223 A model $\M = (\F, V)$ \emph{satisfies} a formula $\varphi$ at time instant $i$ is denoted by $\M,i \models \varphi$. Satisfiability of a formula $\varphi$ is defined inductively over the structure of $\varphi$:
225 \item $\M,i \models p$ for $p \in \Prop \iff p \in V(i)$
226 \item $\M,i \models \neg \varphi \iff$ not $\M,i \models \varphi$
227 \item $\M,i \models \varphi \lor \psi \iff \M,i \models \varphi$ or $\M,i \models \psi$
228 \item $\M,i \models \X \varphi \iff \M,i+1 \models \varphi$
229 \item $\M,i \models \varphi \U \psi \iff \exists{k \geq i}: \M,k \models \psi$ and $\forall{i \leq j < k}: \M,j \models\varphi$
232 \end{def:satisfiability}
234 \begin{def:vocabulary}
235 Let $\varphi$ be an LTL-formula over atomic propositions $\Prop$, we define the \emph{vocabulary} $Voc(\varphi)$ of $\varphi$ inductively:
238 \item $Voc(p) = \{p\}$ for $p \in \Prop$
239 \item $Voc(\neg \varphi) = Voc(\varphi)$
240 \item $Voc(\varphi \lor \psi) = Voc(\varphi) \cup Voc(\psi)$
241 \item $Voc(\X \varphi) = Voc(\varphi)$
242 \item $Voc(\varphi \U \psi) = Voc(\varphi) \cup Voc(\psi)$
246 \noindent Let $\M = (\F, V)$ be a model and $\varphi$ an LTL-formula, we define model $\M_{Voc(\varphi)} = (\F, V_{Voc(\varphi)})$ with:
247 \[\forall{i \in \N}: V_{Voc(\varphi)}(i) = V(i) \cap Voc(\varphi)\]
248 Henceforth, we will abbreviate $\M_{Voc(\varphi)}$ and $V_{Voc(\varphi)}$ with $\M_\varphi$ and $V_\varphi$ accordingly.
249 %\noindent Let $\M$ be a model and $\varphi$ an LTL-formula, we define model $\M_{Voc(\varphi)}$:
250 %\[\forall{i \in \N}: \M_{Voc(\varphi)} = \M(i) \cap Voc(\varphi)\]
253 \begin{prop:vocabulary sat}
254 Let $\M$ be a model and $\varphi$ an LTL-formula, then following holds:
255 \[\forall{i \in \N}: \M,i \models \varphi \iff \M_\varphi,i \models \varphi\]
256 \end{prop:vocabulary sat}
258 \subsection{Derived connectives}
259 \label{sec:derived connectives}
260 For a more convenient description of system specifications, we present some derived symbols to be used in LTL-formulae. At first, we introduce the notion of \emph{truth} and \emph{falsity} using constants $\top$ and $\bot$. Then we expand our set of connectives with the Boolean \emph{and}, \emph{implication} and \emph{equivalence}. And at last we derive the commonly used modal operators \emph{eventually} and \emph{henceforth}.
262 In anticipation of section \ref{sec:on-the-fly methods}, we extend our logic's syntax with the binary connective $\V$, the dual of $\U$, which will become useful in the interpretation known as the \emph{two-state semantics}.
264 Let $\varphi$ and $\psi$ be $L_{LTL}(\Prop)$-formulae:
267 \item $\top \equiv p \lor \neg p$ for $p \in \Prop$
268 \item $\bot \equiv \neg \top$
269 \item $\varphi \land \psi \equiv \neg (\neg \varphi \lor \neg \psi)$
270 \item $\varphi \rightarrow \psi \equiv \neg \varphi \lor \psi$
271 \item $\varphi \leftrightarrow \psi \equiv (\varphi \rightarrow \psi) \land (\psi \rightarrow \varphi)$
272 \item $\Diamond \varphi \equiv \top \U \varphi$
273 \item $\Box \varphi \equiv \neg \Diamond \neg \varphi$
274 \item $\varphi \V \psi \equiv \neg(\neg \varphi \U \neg \psi)$
277 \noindent From the derivations for operators $\Diamond$, \emph{read diamond}, and $\Box$, \emph{read box}, it follows:
280 \item $\M,i \models \Diamond \varphi \iff \exists{k \geq i}: \M,k \models \varphi$
281 \item $\M,i \models \Box \varphi \iff \forall{k \geq i}: \M,k \models \varphi$
285 \noindent With the additional derived connectives we get the following $L_{LTL}(\Prop)$-formulae productions:
286 \[\varphi ::= p \in \Prop \,|\, \neg \varphi \,|\, \varphi \lor \varphi \,|\, \varphi \land \varphi \,|\, \X \varphi \,|\, \varphi \U \varphi \,|\, \varphi \rightarrow \varphi \,|\, \varphi \leftrightarrow \varphi \,|\, \Diamond \varphi \,|\, \Box \varphi\]
288 \section{Automata construction}
289 Before applying the automata-theoretic verification methods, we need to construct the automaton for a given specification formula $\varphi$ and for the program $P$ in test.
291 \subsection{Specification automata}
292 \label{sec:specification automata}
293 For the construction of an automaton $\A_\varphi$ for an LTL-formula $\varphi$, we treat the model $\M = (\F, V)$ for an LTL-formula $\varphi$ as an infinite word over the finite alphabet $2^{Voc(\varphi)}$.
295 \begin{def:rep function}
296 We define the \emph{representation function} $rep: \M \to 2^\Prop$, which returns an infinite word representing the model $\M_\varphi = (\F, V_\varphi)$ over the ordered image $V_\varphi^\rightarrow(\N)$ of its validation function, i.e., $rep(\M_\varphi) = (V_\varphi(0), V_\varphi(1), ...)$. Additionaly, we provide the \emph{inverted representation function} $rep^{-1}: 2^\Prop \to \M$, which compiles an infinite word to the corresponding model, i.e., $rep^{-1}(V_\varphi^\rightarrow(\N)) = \M_\varphi$.
297 \[Mod(\varphi) = \{rep(\M_\varphi) \mid \M_\varphi = (\F, V_\varphi) \land \M_\varphi,0 \models \varphi\}\]
298 $Mod(\varphi)$ is the set of all infinite words, which represent models for $\varphi$.
299 \end{def:rep function}
301 \begin{def:fs closure}
302 \label{def:fs closure}
303 Let $\varphi$ be an LTL-formula, then the \emph{Fischer-Ladner closure} $CL(\varphi)$ of $\varphi$ is the smallest set of formulae such that following holds:
304 %\begin{multicols}{2}
307 \item $\varphi \in CL(\varphi)$
308 \item $\neg \psi \in CL(\varphi) \implies \psi \in CL(\varphi)$
309 \item $\psi \in CL(\varphi) \implies \neg \psi \in CL(\varphi)$
310 \item $\psi \lor \chi \in CL(\varphi) \implies \psi, \chi \in CL(\varphi)$
311 \item $\X \psi \in CL(\varphi) \implies \psi \in CL(\varphi)$
312 \item $\psi \V \chi \in CL(\varphi) \implies \psi, \chi \in CL(\varphi)$
315 \item $\psi \U \chi \in CL(\varphi) \implies \psi, \chi, \X(\psi \U \chi) \in CL(\varphi)$
320 \noindent Let $CL(\varphi)$ be the closure of formula $\varphi$, we define a subset with the \emph{until}-formulae of the closure $\mathbb{U}_\varphi \subseteq CL(\varphi)$ where:
321 \[\mathbb{U}_\varphi = \{\psi \U \chi \mid \psi \U \chi \in CL(\varphi)\} \text{ and } \mathbb{U}_{\varphi_i} \text{ denotes the $i^{th}$ element of } \mathbb{U_\varphi}\]
324 Let $\varphi$ be a formula and $CL(\varphi)$ its closure. $A \subseteq CL(\varphi)$ is an \emph{atom} if following holds:
326 \item $\forall{\psi \in CL(\varphi)}: \psi \in A \iff \neg \psi \notin A$
327 \item $\forall{\psi \lor \chi \in CL(\varphi)}: \psi \lor \chi \in A \iff \psi \in A$ or $\chi \in A$
328 \item $\forall{\psi \U \chi \in CL(\varphi)}: \psi \U \chi \in A \iff \chi \in A$ or $\psi, \X(\psi \U \chi) \in A$
330 We define the set of all atoms of formula $\varphi$ with $\mathbb{AT}_\varphi = \{A \subseteq CL({\varphi}) \mid A \text{ is an atom}\}$.
333 \noindent Now that we have the required ingredients, we begin with the construction of automaton $\A_\varphi$ for formula $\varphi$. Let $\A_\varphi = (\Sigma, S, S_0, \Delta, \{F_i\})$ with:
335 \item $\Sigma = 2^{Voc(\varphi)}$
336 \item $S = \mathbb{AT_\varphi}$
337 \item $S_0 = \{A \in \mathbb{AT_\varphi} \mid \varphi \in A\}$
338 %\item $(A, P, B) \in \Delta$ for $A, B \in \mathbb{AT_\varphi}$ and $P = A \cap Voc(\varphi) \iff (\X \psi \in A \iff \psi \in B)$
339 \item $\Delta = \{(A, P, B) \mid A, B \in \mathbb{AT_\varphi}, P = A \cap Voc(\varphi), \X \psi \in A \iff \psi \in B\}$
340 %\item $\forall{i \in \N, i < k = |\mathbb{U}_{CL(\varphi)}|}: F_i = \{A \in \mathbb{AT}_\varphi \mid \psi \U \chi \notin A$ or $\chi \in A\}$
341 \item $F_i = \{A \in \mathbb{AT}_\varphi \mid \psi \U \chi = \mathbb{U}_{\varphi_i}, \psi \U \chi \notin A$ or $\chi \in A\}$
342 %Let $A, B \in \mathbb{AT}$ and $P \subseteq Voc(\varphi)$. Then $(A, P, B) \in \Delta$ iff the following holds:
343 %$P = A \cap Voc(\varphi)$ and For all $\X \psi \in CL(\varphi): \X \psi \in A$ iff $\psi \in B$.
346 \begin{thm:model language}
347 \label{thm:model language}
348 Let $\M_\varphi = (\F, V_\varphi)$ be a model and $rep(\M_\varphi)$ its infinite representation word, then following holds:
349 \[rep(\M_\varphi) \in L_\omega(\A_\varphi) \iff \M_\varphi,0 \models \varphi\]
350 \end{thm:model language}
353 For the eloberate proof, consult \cite{ref:ltl&büchi}.
355 \begin{cor:mod=model language}
356 \label{cor:mod=model language}
357 From Theorem \ref{thm:model language} follows $Mod(\varphi) = L_\omega(\A_\varphi)$.
358 \end{cor:mod=model language}
360 \subsection{Program automata}
361 In the next step, we model a given program $P$ as automaton $\A_P$. A program is a structure $P = (S_P, s_0, R, V)$, where $S$ is the set of possible states of the program, $s_0$ the initial state, $R : S \times \Prop \times S$ the transition relation and $V : S \to 2^\Prop$ a valuation function. A \emph{computation} of $P$ is a run $\rho = (V(s_0), V(s_1), ...)$.
363 We construct automaton $\A_P = (\Sigma, S, S_0, \Delta, F)$, with:
366 \item $\Sigma = 2^\Prop$
368 \item $S_0 = \{s_0\}$
372 \item $\Delta = \{(s, V(s), s') \mid \exists{a \in \Prop}: (s, a, s') \in R\}$
374 In practical verification of programs, the specification covers only the properties of a system, which are vital to the program's correctness, where our program description contains all details of all possible execution paths. Let $\varphi$ be the specification formula, we can reduce the state exploration to the vocabulary of $\varphi$ by the reduction of the transition relation to $\Delta = \{(s, A, s') \mid \exists{a \in \Prop}: (s, a, s') \in R \land A = V(s) \cap Voc(\varphi)\}$.
376 \begin{prop:computation set=language}
377 \label{prop:computation set=language}
378 Let $\A_P = (\Sigma, S, S_0, \Delta, F)$, for $F = S$ it follows that each run of $\A_P$ is accepting, therefore is $L_\omega(\A_P)$ the set of all computations of $P$.
379 \[L_\omega(\A_P) = \{\rho \mid \rho \text{ is a run of } \A_P\}\]
380 \end{prop:computation set=language}
382 We can view each run of $\A_P$, i.e., each computation of $P$, as a representation of model $\M_\rho = (\F, V)$, where $\F$ is a frame and $V$ the program's valuation function. In analogy to the specification, we define:
383 \[Mod(P) = \{\rho \mid \rho \text{ is a computation of } P\}\]
384 \begin{cor:mod=program language}
385 \label{cor:mod=program language}
386 From Theorem \ref{thm:model language} and Proposition \ref{prop:computation set=language} follows $Mod(P) = L_\omega(\A_P)$.
387 \end{cor:mod=program language}
389 \section{Model checking}
390 For effective automata-theoretic verification of reactive programs, we have modelled the program as a non-deterministic B\"uchi automaton $\A_P$ and the specification formula $\varphi$ as automaton $\A_\varphi$.
392 Given a program $P$ and specification $\varphi$, the verification problem is the following: \emph{does every run of $P$ satisfy $\varphi$?} To show this we use the previously introduced automata constructions and reduce the problem to $L_\omega(\A_P) \subseteq L_\omega(\A_\varphi)$, i.e., all runs accepted by $\A_P$ are also accepted by $\A_\varphi$. By this problem definition, we clearly have to explore the whole state space of $\A_\varphi$ for each run of $\A_P$. This prevents efficient on-demand constructions. Therefore we rephrase the problem with the contrapositive definition $L_\omega(\A_P) \cap \overline{L_\omega(\A_\varphi)} = \emptyset$, where $\overline{L_\omega(\A_\varphi)} = \Sigma^\omega - L_\omega(\A_\varphi) = L_\omega(\A_{\neg \varphi})$ \cite{ref:alternating verification}.
394 In conclusion, the essence of model checking lies within the test for emptyness of the intersection between the recognised language of the program automaton and the recognised language of the automaton for its negated specification:
395 \[L_\omega(\A_P) \cap L_\omega(\A_{\neg \varphi}) = \emptyset\]
397 \begin{thm:model checking}
398 \label{thm:model checking}
399 Let $P$ be a finite-state program and $\A_P$ its automaton, let $\varphi$ be an LTL-formula and $\A_\varphi$ its automaton. P satisfies $\varphi$ iff $L_\omega(\A_P) \cap L_\omega(\A_{\neg \varphi}) = \emptyset$.
400 \end{thm:model checking}
402 \noindent From Corollary \ref{cor:mod=model language} and \ref{cor:mod=program language} follows:
403 \[L_\omega(\A_P) \cap L_\omega(\A_{\neg \varphi}) = \emptyset \iff Mod(P) \cap Mod(\neg \varphi) = \emptyset\]
405 \subsection{Complexity}
406 Let the size $|P|$ of a program $P = (S, s_0, R, V)$ be proportional to the sum of its structural components, i.e., $|P| = |S| + |R|$. The size $|\varphi|$ is the length of the formula string. The asymptotical complexity of the presented automata-theoretic verification method is in time $O(|P| \cdot 2^{O(|\varphi|)})$ \cite{ref:concurrent checking}.
408 The size of $\varphi$ is usually short \cite{ref:concurrent checking}, so the exponential growth by it is reasonable. Generally, the number of states is at least exponential in the size of its description by means of a programming language. This concludes, that despite that the upper bound is polynomial in the size of the program, in practice, we are facing exponential growth in complexity \cite{ref:handbook}.
410 \section{On-the-fly methods}
411 \label{sec:on-the-fly methods}
412 The automata-theoretic approach on verification in Theorem \ref{thm:model checking} requires a fully constructed automaton for the specification, when applying the graph-theoretic emptyness test.
414 A more space-efficient strategy is the on-the-fly construction of the automaton during a depth-first search, short DFS. The DFS explores the product states of both automata incrementally, testing for cycles in each iteration. If the program does not satisfy a formula, an accepting cycle will occur and lead to termination of the search. In the case of a valid program, i.e., the program does meet the specification, no cycles will occur. In the latter case, such a strategy would inevitably explore the whole state space of the automata.
416 \subsection{Two-state semantics}
417 For the successful incremental construction of automata, we provide a new interpretation for the infinite computation paths. By applying temporal reasoning, we separate the computation paths in two states, incrementally for each time instant. The two states resemble the satisfiability requirements for any time instant $i$ and its successor $i+1$.
419 \subsubsection{Example}
420 Let $\varphi = a \U b$. We apply the two-state semantics on $\varphi$ and it follows:
421 \[\forall{i \in \N}: \M,i \models \varphi \iff \M,i \models b \text{ or } \M,i+1 \models a \land \X(\varphi)\]
422 In this example, we construct the specification automaton incrementally for each time instant; the states are constructed from the union of the current-state and next-state requirements $\{b\} \cup \{a, \X(\varphi)\}$.
424 Let us formalise the notion of the incremental automaton construction based on the idea of the two-state semantics.
426 \begin{def:positive formulae}
427 Let $\Prop$ be a set of atomic propositions and let $\overline{\Prop} = \{\neg p \mid p \in \Prop\}$. We define the set of LTL-formulae in \emph{positive form}:
428 \[\Phi^+ = \Prop \cup \overline{\Prop} \cup \{\top, \bot\} \cup \{\varphi \lor \psi, \varphi \land \psi, \X\varphi, \varphi \U \psi, \varphi \V \psi \mid \varphi, \psi \in \Phi^+\} \]
429 \end{def:positive formulae}
431 The positive form of a formula contains only negations at the level of atomic propositions. This is the reason for the introduction of the dual $\V$ in \ref{sec:derived connectives}; to provide a way of shifting the negation of $\U$-formulae inwards by the substitution with its contrapositive form.
434 Let $\Phi$ be a set of LTL-formulae, we define:
435 \[next(\Phi) = \{ \X\varphi \mid \X\varphi \in \Phi\} \text{ and } snext(\Phi) = \{ \varphi \mid \X\varphi \in \Phi\}\]
439 Let $\Phi^+$ be the set of LTL-formulae in positive form and let $Q = \Prop \cup \overline{\Prop} \cup next(\Phi^+)$. We define the function $\dnf: \Phi^+ \to 2^Q$ inductively:
441 &\dnf(\top) &= &\, \{\emptyset\}\\
442 &\dnf(\bot) &= &\, \emptyset\\
443 &\dnf(x) &= &\, \{\{x\}\}, \text{ for } x = p, \neg p, \X\varphi\\
444 &\dnf(\varphi \lor \psi) &= &\, \dnf(\varphi) \cup \dnf(\psi)\\
445 &\dnf(\varphi \land \psi) &= &\, \{C \cup D \mid C \in \dnf(\varphi), D \in \dnf(\psi), C \cup D \text{ is consistent}\}\\
446 &\dnf(\varphi \U \psi) &= &\, \dnf(\varphi \land \X(\varphi \U \psi)) \cup \dnf(\psi)\\
447 &\dnf(\varphi \V \psi) &= &\, \dnf(\varphi \land \psi) \cup \dnf(\psi \land \X(\varphi \V \psi))
450 \noindent The disjunctive normal form provides the partitioning for the automata state construction over the two-state semantics. The modal connectives $\U$ and $\V$ are interpreted as disjunctions over the path of computation.
453 Let $\Phi^+$ be the set of formulae in positive form and let $\M_\varphi$ be a model over the vocabulary of $\varphi$ then following holds:
454 \[\forall{\varphi \in \Phi^+}: \M_\varphi,0 \models \varphi \iff \M_\varphi,0 \models \bigvee_{D \in \dnf(\varphi)} \bigwedge D\]
458 Let $C \subseteq CL(\varphi)$, then $\consq(C)$ is the smallest subset of $CL(\varphi)$ such that following holds:
462 \item $C \subseteq \consq(C)$
463 \item $\top \in \consq(C)$, if $\top \in CL(\varphi)$
466 \item $\psi \lor \chi \in \consq(C)$, if $\psi \lor \chi \in CL(\varphi)$ and $\psi \in \consq(C) \lor \chi \in \consq(C)$
467 \item $\psi \land \chi \in \consq(C)$, if $\psi \land \chi \in CL(\varphi)$ and $\psi, \chi \in \consq(C)$
468 \item $\psi \U \chi \in \consq(C)$, if $\psi \U \chi \in CL(\varphi)$ and $\psi, \X(\psi \U \chi) \in \consq(C) \lor \chi \in \consq(C)$
469 \item $\psi \V \chi \in \consq(C)$, if $\psi \V \chi \in CL(\varphi)$ and $\psi, \X(\psi \U \chi) \in \consq(C) \lor \psi, \chi \in \consq(C)$
475 Let $\psi \in CL(\varphi)$, let $C, D \subseteq CL(\varphi)$ and let $\M$ be a model, then following holds:
478 \item $\consq(C) \subseteq \consq(D)$, if $C \subseteq D$
479 \item $\psi \in \consq(C)$, if $C \in \dnf(\psi)$
480 \item $\psi \in \consq(D)$, if $\psi \in C \land D \in \dnf(\bigwedge C)$
481 \item $\M,0 \models \bigwedge \consq(C)$, if $\M,0 \models \bigwedge C$
486 \begin{def:partial automata}
487 Let $\varphi$ be a formula with its disjunctive normal form $\dnf(\varphi)$ and let $Q = \Prop \cup \overline{\Prop} \cup next(CL(\varphi))$. Again we use the subset $\mathbb{U}_\varphi \subseteq CL(\varphi)$ of \emph{until}-formulae of the closure as defined in \ref{def:fs closure}. We define the \emph{partial automaton} $\A_\varphi = (\Sigma, S, S_0, \Delta, \{F_i\})$ with:
489 \item $\Sigma = 2^{Voc(\varphi)}$
491 \item $S_0 = \dnf(\varphi)$
492 \item $\Delta = \{(A, P, B) \mid \A \cap \Prop \subseteq P$ and $\{p \mid \neg p \in A\} \cap P = \emptyset$ and $B \in \dnf(\bigwedge snext(A)) \}$
493 \item $F_i = \{A \in S \mid \psi \U \chi = \mathbb{U}_{\varphi_i}$ and $\psi \U \chi \notin \consq(A) \lor \chi \in \consq(A) \}$
495 \end{def:partial automata}
497 \noindent The soundness and completeness proofs are provided in \cite{ref:ltl&büchi}; the equivalance of the partial automata and the specification automata as defined in \ref{sec:specification automata} follows from the proofs.
499 \subsection{On-the-fly construction}
505 \REQUIRE $Node, NodeSet$
506 \IF {$New(Node) = \emptyset$}
507 \IF {$\exists{N \in NodeSet}: Old(N) = Old(Node)$ and $Next(N) = Next(Node)$}
508 \STATE $Incoming(N) = Incoming(N) \cup Incoming(Node)$
512 \IF {$i+k\leq maxval$}
519 \section*{Discussion}
520 Linear-Time Temporal Logic and B\"uchi Automata \cite{ref:ltl&büchi} is an in-depth introduction to automated verification. It delivers the core concepts of model checking in a readable way. The formal proofs are clean and absorbable. The introduction section provides a good overview of the structure of the text and the basic theory behind all concepts.
522 However, the author does not make any efforts to deliver a motivation for the topic. From the beginning, the substance of the text resides within the world of model checking, without an external view on the practical applications and their significance.
524 At some points, the definitions are either lacking formality or are inconsistent. It seemes like several concepts are introduced ad-hoc and without rigor. In an introductory text, such inaccuracies may lead to confusion and diminished confident in the reader's own understanding of the discussed topics.
528 \begin{thebibliography}{99}
529 \bibitem{ref:ltl&büchi}
530 \uppercase{M{\footnotesize adhavan} M{\footnotesize ukund}.}
531 {\em Linear-Time Temporal Logic and B\"uchi Automata}.
532 Winter School on Logic and Computer Science, Indian Statistical Institute, Calcutta, 1997.
534 \bibitem{ref:alternating verification}
535 \uppercase{M{\footnotesize oshe} Y. V{\footnotesize ardi}.}
536 {\em Alternating Automata and Program Verification}.
537 Computer Science Today, Volume 1000 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1995.
539 \bibitem{ref:automated verification}
540 \uppercase{M{\footnotesize oshe} Y. V{\footnotesize ardi}.}
541 {\em Automated Verification: Graphs, Logic and Automata}.
542 Proceeding of the International Joint Conference on Artificial Intelligence, Acapulco, 2003.
544 \bibitem{ref:on-the-fly verification}
545 \uppercase{R{\footnotesize ob} G{\footnotesize erth,} D{\footnotesize oron} P{\footnotesize eled,} M{\footnotesize oshe} Y. V{\footnotesize ardi and} P{\footnotesize ierre} W{\footnotesize olper}.}
546 {\em Simple On-the-fly Automatic Verification of Linear Temporal Logic}.
547 Proceeding IFIO/WG6.1 Symposium on Protocol Specification, Testing and Verification, Warsaw, 1995.
549 \bibitem{ref:concurrent checking}
550 \uppercase{O{\footnotesize rna} L{\footnotesize ichtenstein and} A{\footnotesize mir} P{\footnotesize nueli}.}
551 {\em Checking that finite state concurrent programs satisfy their linear specification}.
552 Proceeding 12th ACM Symposium on Principles of Programming Languages, New York, 1985.
554 \bibitem{ref:infpaths}
555 \uppercase{P{\footnotesize ierre} W{\footnotesize olper},
556 M{\footnotesize oshe} Y. V{\footnotesize ardi and}
557 A. P{\footnotesize rasad} S{\footnotesize istla}.}
558 {\em Reasoning about Infinite Computation Paths}.
559 Proceedings of the 24th IEEE FOCS, 1983.
561 \bibitem{ref:handbook}
562 \uppercase{P{\footnotesize atrick} B{\footnotesize lackburn},
563 F{\footnotesize rank} W{\footnotesize olter and} J{\footnotesize ohan van} B{\footnotesize enthem}.}
564 {\em Handbook of Modal Logic (Studies in Logic and Practical Reasoning)}.
565 3rd Edition, Elsevier, Amsterdam, Chapter 11 P. 655-720 and Chapter 17 P. 975-989, 2007.
566 \end{thebibliography}