1.1 --- a/paper/src/paper.tex Thu Jul 14 03:09:53 2011 +0200
1.2 +++ b/paper/src/paper.tex Fri Jul 15 03:05:50 2011 +0200
1.3 @@ -86,7 +86,7 @@
1.4 %\itshape
1.5 %\renewcommand\abstractname{Abstract}
1.6 \begin{abstract}
1.7 -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.
1.8 +Algorithmic verification is an application of automated temporal reasoning based on model checking. We use the power of modal logics to specify system 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 the automata-theoretic constructions and space-efficient on-the-fly methods for the verification of reactive systems.
1.9 %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.
1.10 \end{abstract}
1.11 %\normalfont
1.12 @@ -94,7 +94,7 @@
1.13 \section{Introduction}
1.14 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.
1.15
1.16 -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.
1.17 +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 lives in car accidents. When handling such critical systems, it becomes inevitable to verify the correctness of such software solutions.
1.18
1.19 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.
1.20
1.21 @@ -102,7 +102,7 @@
1.22
1.23 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.
1.24
1.25 -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.
1.26 +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 program specification language.
1.27
1.28 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.
1.29
1.30 @@ -156,7 +156,7 @@
1.31 \end{def:omega regular languages closure}
1.32
1.33 \section{B\"uchi automata}
1.34 -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.
1.35 +Automata theory is the foundation of state-based modeling 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.
1.36
1.37 \begin{def:buechi automata}
1.38 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$.
1.39 @@ -166,14 +166,14 @@
1.40 Within this text \emph{automaton} will refer to the non-deterministic B\"uchi automaton, unless otherwise noted.
1.41 \end{def:buechi automata}
1.42
1.43 -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.
1.44 +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 modeling non-terminating systems. First, we need to define the legal sequence of state transitions of an automaton when reading an infinite input word.
1.45
1.46 \begin{def:automata runs}
1.47 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.
1.48 \end{def:automata runs}
1.49
1.50 \begin{def:automata acceptance}
1.51 -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$.
1.52 +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 occurrences, i.e., $s$ occurs infinitely often in $\rho$.
1.53
1.54 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}.
1.55
1.56 @@ -183,10 +183,10 @@
1.57 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.
1.58
1.59 \subsection{Generalised B\"uchi automata}
1.60 -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.
1.61 +In the following two sections, we present the modal logic, which is 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.
1.62
1.63 \begin{def:general automata}
1.64 -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$.
1.65 +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{accepting states} $F_i$ are composed within a finite set with $F_i \subseteq S$.
1.66 \end{def:general automata}
1.67
1.68 \begin{def:general acceptance}
1.69 @@ -194,13 +194,13 @@
1.70 \end{def:general acceptance}
1.71
1.72 \begin{prop:general equiv}
1.73 -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:
1.74 +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 equivalence condition holds:
1.75 \[L_\omega(\A) = \bigcap_{i < k} L_\omega(\A_i)\]
1.76 \end{prop:general equiv}
1.77 -\noindent The equivalance of the language recognition abilities of general and non-deterministic B\"uchi automata follows intuitively.
1.78 +\noindent The equivalence of the language recognition abilities of general and non-deterministic B\"uchi automata follows intuitively.
1.79
1.80 \section{Linear temporal logic}
1.81 -Nothing escapes time, but time has successfully escaped its capture 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: historians prefer the past tense, while politicians only make promises for the future. Physicists know 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.
1.82 +Nothing escapes time, but time has successfully escaped its capture 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: historians prefer the past tense, while politicians make only promises for the future. Physicists know 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.
1.83
1.84 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}, short LTL, and \emph{branching temporal logic}, short CTL -- for computation tree logic. Throughout this text, we will restrict our attention to linear temporal logic.
1.85
1.86 @@ -236,7 +236,7 @@
1.87 %
1.88 \noindent From the strict linear order of the LTL-frame accessibility relation follows that an LTL-formula $\varphi$ is \emph{satisfiable}, iff there exists a model $\M$ with $\M,0 \models \varphi$.
1.89
1.90 -We clearly see, that atomic propositions, which are not contained within the formula $\varphi$ are redundant to the the definition of the satisfiablity. By defining the \emph{vocabulary} of a formula, we dispose such irrelevant atomic proposition from the alphabet.
1.91 +We clearly see, that atomic propositions, which are not contained within the formula $\varphi$ are redundant to the the definition of the satisfiability. By defining the \emph{vocabulary} of a formula, we dispose such irrelevant atomic proposition from the alphabet.
1.92
1.93 \begin{def:vocabulary}
1.94 Let $\varphi$ be an LTL-formula over atomic propositions $\Prop$, we define the \emph{vocabulary} $Voc(\varphi)$ of $\varphi$ inductively:
1.95 @@ -300,7 +300,7 @@
1.96 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)}$.
1.97
1.98 \begin{def:rep function}
1.99 -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$.
1.100 +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), ...)$. Additionally, 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$.
1.101 \[Mod(\varphi) = \{rep(\M_\varphi) \mid \M_\varphi = (\F, V_\varphi) \land \M_\varphi,0 \models \varphi\}\]
1.102 $Mod(\varphi)$ is the set of all infinite words, which represent models for $\varphi$.
1.103 \end{def:rep function}
1.104 @@ -357,7 +357,7 @@
1.105 \end{thm:model language}
1.106 \noindent
1.107 \begin{proof}
1.108 -For the eloberate proof, consult \cite{ref:ltl&büchi}.
1.109 +For the elaborate proof, consult \cite{ref:ltl&büchi}.
1.110 \end{proof}
1.111 \begin{cor:mod=model language}
1.112 \label{cor:mod=model language}
1.113 @@ -394,11 +394,11 @@
1.114 \end{cor:mod=program language}
1.115
1.116 \section{Model checking}
1.117 -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$.
1.118 +For effective automata-theoretic verification of reactive programs, we have modeled the program as a non-deterministic B\"uchi automaton $\A_P$ and the specification formula $\varphi$ as automaton $\A_\varphi$.
1.119
1.120 -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}.
1.121 +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 contra-positive 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}.
1.122
1.123 -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:
1.124 +In conclusion, the essence of model checking lies within the test for emptiness of the intersection between the recognised language of the program automaton and the recognised language of the automaton for its negated specification:
1.125 \[L_\omega(\A_P) \cap L_\omega(\A_{\neg \varphi}) = \emptyset\]
1.126
1.127 \begin{thm:model checking}
1.128 @@ -410,13 +410,13 @@
1.129 \[L_\omega(\A_P) \cap L_\omega(\A_{\neg \varphi}) = \emptyset \iff Mod(P) \cap Mod(\neg \varphi) = \emptyset\]
1.130
1.131 \subsection{Complexity}
1.132 -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}.
1.133 +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 asymptotic complexity of the presented automata-theoretic verification method is in time $O(|P| \cdot 2^{O(|\varphi|)})$ \cite{ref:concurrent checking}.
1.134
1.135 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}.
1.136
1.137 \section{On-the-fly methods}
1.138 \label{sec:on-the-fly methods}
1.139 -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.
1.140 +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 emptiness test.
1.141
1.142 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.
1.143
1.144 @@ -435,7 +435,7 @@
1.145 \[\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^+\} \]
1.146 \end{def:positive formulae}
1.147
1.148 -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.
1.149 +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 contra-positive form.
1.150
1.151 \begin{def:next}
1.152 Let $\Phi$ be a set of LTL-formulae, we define:
1.153 @@ -501,14 +501,14 @@
1.154 \end{itemize}
1.155 \end{def:partial automata}
1.156
1.157 -\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.
1.158 +\noindent The soundness and completeness proofs are provided in \cite{ref:ltl&büchi}; the equivalence of the partial automata and the specification automata as defined in \ref{sec:specification automata} follows from the proofs.
1.159
1.160 \subsection{On-the-fly construction}
1.161 The sequential description of the program design makes it trivial to incrementally construct the program automaton state by state. The more difficult part is the construction of the partial specification automaton on-the-fly.
1.162
1.163 To archive this, we begin with a set of states built by applying $\dnf(\varphi)$. In the next step we determine a state within the current set of states, which is consistent with the program automaton. We use this state to expand its successor states. Now, we analyse the expanded state space for cycles. If no cycles are detected, we repeat this procedure, while there are still consistent states left.
1.164
1.165 -When the procedure terminates, we check whether the specification automaton was fully built. If that is the case, we have explored the whole state space of both automata and have not found any cycles, i.e., the program does satisfy the specification. Otherwise, the procedure was prematurally aborted by a cycle detection, i.e., the program does satisfy the \emph{negated} specification and therefore does \emph{not} meet the specification properties.
1.166 +When the procedure terminates, we check whether the specification automaton was fully built. If that is the case, we have explored the whole state space of both automata and have not found any cycles, i.e., the program does satisfy the specification. Otherwise, the procedure was prematurely aborted by a cycle detection, i.e., the program does satisfy the \emph{negated} specification and therefore does \emph{not} meet the specification properties.
1.167
1.168 \begin{algorithm}
1.169 \caption{expand: $\Phi^+ \times 2^Q \to 2^Q$}
1.170 @@ -538,9 +538,9 @@
1.171 \section*{Discussion}
1.172 \emph{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 comprehensible way. The formal proofs are clean and well absorbable. The referenced material effectively fills the gaps, when looking for more detailed explanations, e.g. about the on-the-fly method. Some few, but good examples support the substantiation of the theoretic material. The introduction section provides a good overview of the text structure and the basic theory behind most concepts used.
1.173
1.174 -However, the author does not make an effort 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 the significance of formal verification to the industry remains unclear.
1.175 +However, the author does not make an effort 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, the significance of formal verification to the industry remains unclear.
1.176
1.177 -A few definitions are either lacking formality or are inconsistent. It seems like several concepts are introduced ad-hoc and without rigor. In an introductory text, such inaccuracies may lead to confusion and distract the reader's attention from the essence of the topic.
1.178 +A few definitions are either lacking formality or are inconsistent. It seems like several concepts are introduced ad-hoc and without rigor. In an introductory text, such inaccuracies may lead to confusion and divert the reader's attention from the essence of the presented topic.
1.179
1.180 \begin{thebibliography}{99}
1.181 \bibitem{ref:ltl&büchi}