Previous chapter: Büchi’s Characterization Theorem

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Introduction

In the theory of automata over finite words, we have Rabin-Scott powerset construction, which converts a nondeterministic automaton over finite words into a deterministic automaton that recognizes the same language. This shows that nondeterminism does not make automata over finite words more expressive (but makes it more concise as the construction produces an exponential number of states).

The situation is different for Büchi automata: even though the language $L = (a+b)^*b^\omega$ is clearly Büchi-recognizable, there is, as the following theorem shows, no deterministic Büchi automaton that recognizes L.

Deterministic vs. nondeterministic Büchi automata

$\textbf{Theorem 4.1. }\textit{Language $L=(a+b)^*b^\omega$ is not recognizable by deterministic Büchi Automata}$

Starting a base case $b^\omega$, we add $(a+b)$ as the prefix one by one. Can we express the kleene star?
That is, is the automaton only accept finitely many $(a+b)$?

Proof

Assume, by way of contradiction, that $L$ is recognizable by the deterministic Büchi automaton $\mathcal{A}=(\Sigma,Q,I,T,\small\text{BÜCHI}\normalsize(F))$. Since $\alpha_0=b^\omega$ is in $L$, there is an unique run

Previous chapter: Closure Properties of the Büchi-recognizable languages (Concatenations)

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

We are now ready to prove Büchi’s Characterization Theorem, a result from 1962.

$\textbf{Theorem 3.6. }\text{(Büchi’s Characterization Theorem) }$ $\textit{An $\omega$-language is Büchi-recognizable iff it is $\omega$-regular.}$

Explained in Human language

p.s. Büchi-recognizable means the language can be described by a Büchi automata.

“$\Leftarrow$”
We have to prove if the language is $\omega$-regular, then it is Büchi-recognizable.
In section 3.2, we learn that an $\omega$-regular language contains 3 operators:

• union of $\omega$-regular languages, $W_1+W_2$ (proved by Theorem 3.2),
• infinite concatenation of a non-empty regular language $E^\omega$ (proved by Theorem 3.4), and
• concatenation of regular languages and $\omega$-regular language $E\cdot W$ (proved by Theorem 3.5)

“$\Rightarrow$”
We have to prove if the language is Büchi-recognizable, then it is $\omega$-regular.
Here, we try to construct a Büchi-recognizable using all $\omega$-regular operators.

We begin by constructing a regular language $W_{q,q’}$. Words of the language $w$ is accepted by some finite-word automata, with a pair of state $q,q’\in Q$ being the initial and accepting states respectively.

Previous chapter: Closure Properties of the Büchi-recognizable languages (Intersection and Union)

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

In this section, we continue the proof of the closure properties of the Büchi-recognizable languages.

Concatenation of regular Langauge and Büchi-recognizable Language

$\textbf{Construction 3.3. } \text{Let }\mathcal{A}_1=(\Sigma,Q_1,I_1,T_1,F_1)\text{ be an automaton over finite words that}$ $\text{recognizes the languge }L_1\text{, and let }\mathcal{A}_2 = (\Sigma,Q_2,I_2,T_2,\small\text{BÜCHI}\normalsize (F_2))\text{ be a Büchi automaton}$ $\text{over the same alphabet that recognizes }L_2.\text{ We construct a Büchi autotmaton }$ $\mathcal{A’}=(\Sigma,Q’,I’,T’,\small\text{BÜCHI}\normalsize (F_2))\text{ with }\mathcal{L}(\mathcal{A’})=L_1\cdot L_2\text{ as follows:}$

$\begin{array}{lrll}
\hspace{1cm} \cdot &Q’&=&Q_1\cup Q_2 \hspace{0.7cm}(\text{w.l.o.g we assume }Q_1\cap Q_2=\varnothing)\newline
\hspace{1cm} \cdot &I’&=&\biggl\lbrace \begin{array}{ll}I_1 & \ \text{if }I_1\cap F_1=\varnothing\newline
I_1\cup I_2 & \ \text{otherwise}\end{array} \newline
\hspace{1cm} \cdot &T’&=&T_1\cup T_2\cup\lbrace (q,\sigma,q’)\mid(q,\sigma,f)\in T_1,f\in F_1,q’\in I_2\rbrace \newline
\end{array}$

Notation	Explaination
$Q’$	Same as Union, we include both automata for concatenation
$I’$	We normaly start the the automaton from $I_1$ If $I_1$ is non-empty, otherwise we start at $I_2$
$T’$	For any states that can reach the accepting states of $T_1$ with one transition, we create a new transitions that reach the initial states of $T_2$ $(I_2)$

The correctness of this construction is proven by the following theorem.

$\textbf{Theorem 3.4. }$ $\text{If }\textit{$L_1$ is a regular language and $L_2$ is Büchi-recognizable, then $L_1\cdot L_2$ is Büchi-recognizable.}$

Explained in Human language

If $I_1$ is non-empty, then we can have a run that starts from $I_1$ to $r(n)$, that is one transition before $\mathcal{A_1}$’s accepting states of $f$. Then for next transition we either move to $f$, or we move on to $\mathcal{A_2}$ starting from $r(n+1)$.

Previous chapter: $\omega$-regular language

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

In the following we refer the languages recognized by Büchi automata simply as Büchi-recognizable languages. Büchi’s characterization theorem states that the $\omega$-regular languages are exactly Büchi-recognizable languages. To prepare for the proof of Büchi’s theorem, we establish several closure properties of the Büchi-recognizable languages.

Closure Properties of Language Union

$\textbf{Construction 3.1. } \text{Let }L_1\text{ and }L_2\text{ be }\omega\text{-languages recognized by the Büchi automata}$ $\mathcal{A}_1=(\Sigma,Q_1,I_1,T_1,\small\text{BÜCHI}\normalsize (F_1))\text{ and }\mathcal{A}_2 = (\Sigma,Q_2,I_2,T_2,\small\text{BÜCHI}\normalsize (F_2))\text{, respectively.}$ $\text{We construct }\mathcal{A}_\cup=(\Sigma, Q_\cup, I_\cup,T_\cup,\small\text{BÜCHI}\normalsize (F_\cup))\text{ with }\mathcal{L}(\mathcal{A}_\cup)=L_1\cup L_2\text{ as follows:}$
$\begin{array}{l}\newline
\hspace{1cm} \cdot \ Q_\cup=Q_1\cup Q_2 \hspace{1cm}(\text{w.l.o.g we assume }Q_1\cap Q_2=\varnothing)\newline
\hspace{1cm} \cdot \ I_\cup=I_1\cup I_2 \ \hspace{1cm} \cdot \ T_\cup=T_1\cup T_2 \ \hspace{1cm} \cdot \ F_\cup=F_1\cup F_2 \newline
\end{array}$

The correctness of this construction is proven by the following theorem.

$\textbf{Theorem 3.2. }\text{If }\textit{$L_1$ and $L_2$ are Büchi-recognizable, then so is $L_1\cup L_2$.}$

Formal Proof

We prove that the Büchi automaton $\mathcal{A}_\cup$ built by $\mathcal{A}_1$ and $\mathcal{A}_2$ indeed recognizes the union of the languages of the two automata.

$\mathcal{L}(\mathcal{A}_\cup)\subseteq\mathcal{L}(\mathcal{A}_1)\cup\mathcal{L}(\mathcal{A}_2):$

Previous chapter: Kleene’s Theorem

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Introduction

$\omega$-regular expression denotes languages over infinite words.
In addition to language union on languages over infinite words, we have 2 operations that convert languages over finite words into languages over infinite words.

$\omega$-regular expression

The collection of $\omega$-regular languages over an alphabet $\Sigma^\omega$ is $\mathcal{L}(W)$, where $W$ is a $\omega$-regular expression.
$\omega$-regular expression can be defined as $W := E^\omega \mid E\cdot W\mid W_1+W_2 $, where:

• infinite concatenation of a non-empty regular language $E^\omega$,
• union of $\omega$-regular languages, $W_1+W_2$, and
• concatenation of regular languages and $\omega$-regular language $E\cdot W$

$\textbf{Definition 3.3. } \textit{$\omega$-Regular expressions } \text{are defined as follows:}$
$\begin{array}{l}
\hspace{1cm} \cdot \ \text{If $E$ is a regular expression where $\varepsilon\notin\mathcal{L}(E)$, then $E^\omega$ is an $\omega$-regular expression.}\newline
\hspace{1cm} \ \ \mathcal{L}(E^\omega) = \mathcal{L}(E)^\omega\newline
\hspace{1cm} \ \ \text{where } L^\omega =\lbrace \omega_0\omega_1\dots\mid\omega_i\in L,|\omega_i|>0\rbrace \text{ for } L\subseteq\Sigma^* \newline
\hspace{1cm} \cdot \ \text{If $E$ is a regular expression and $W$ is an $\omega$-regular expression,}\newline
\hspace{1cm} \ \ \text{then $E\cdot W$ is an $\omega$-regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E\cdot W) = \mathcal{L}(E)\cdot\mathcal{L}(W)\newline
\hspace{1cm} \ \ \text{where } L_1 \cdot L_2=\lbrace \omega\alpha\mid\omega\in L_1,\alpha\in L_2\rbrace \text{ for } L_1 \subseteq\Sigma^*, L_2 \subseteq\Sigma^\omega\newline
\hspace{1cm} \cdot \ \text{If $W_1$ and $W_2$ are $\omega$-regular expressions, then $W_1+W_2$ is an $\omega$-regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(W_1+W_2) = \mathcal{L}(W_1)\cup\mathcal{L}(W_2) .\newline
\end{array}$

A language over infinite words is $\omega$-regular if it is definable by a $\omega$-regular expression.

---

Previous chapter: The Büchi Acceptance Condition

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Introduction

Kleene’s theorem states that the set of languages over finite words that can be defined by regular expressions is exactly the set of languages that can be recognized by automata over finite words.

Based on this, we define $\omega$-regular expressions, and finally prove the corresponding theorem for $\omega$-regular languages: Büchi’s characterization theorem.

Regular Expression

Regular expression consist of constants that denote languages of finite words, and
consist of operator symbols that denote operations over these languages.

The collection of regular languages over an alphabet $\Sigma$ is $\mathcal{L}(E)$, where $E$ is a regular expression.
Regular expression can be defined as $E := \varepsilon\mid\varnothing\mid a\in\Sigma\mid E+F\mid E\cdot F\mid E^* $, where:

• empty language: $\varepsilon$,
• empty string language: $\varnothing$,
• singleton language: (single letter from alphabet) $a\in\Sigma$,
• union of regular languages: $E+F$,
• concatenation of regular languages: $E\cdot F$, and
• language with kleene star: $E^*$.

$\textbf{Definition 3.1. } \textit{Regular expressions } \text{are defined as follows:}$
$\begin{array}{l}\hspace{1cm} \cdot \ \text{The constants }\varepsilon\text{ and }\varnothing\text{ are regular expressions.}\newline
\hspace{1cm} \ \ \mathcal{L}(\varepsilon) = \lbrace\varepsilon\rbrace ,\mathcal{L}(\varnothing)=\varnothing.\newline
\hspace{1cm} \cdot \ \text{If }a\in\Sigma\text{ is a symbol, then }a\text{ is a regular expressions.}\newline
\hspace{1cm} \ \ \mathcal{L}(a) = \lbrace a\rbrace .\newline
\hspace{1cm} \cdot \ \text{If }E\text{ and }F\text{ are regular expressions, then }E+F\text{ is a regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E+F) = \mathcal{L}(E)\cup\mathcal{L}(F) .\newline
\hspace{1cm} \cdot \ \text{If }E\text{ and }F\text{ are regular expressions, then }E\cdot F\text{ is a regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E\cdot F) = \lbrace uv\mid u\in\mathcal{L}(E),v\in\mathcal{L}(F)\rbrace.\newline
\hspace{1cm} \cdot \ \text{If }E\text{ is a regular expression, then }E^*\text{ is a regular expression.}\newline
\hspace{1cm} \ \ \mathcal{L}(E^{\ast}) = \lbrace u_1u_2\dots u_n\mid n\in\mathbb{N},u_i\in\mathcal{L}(E)\text{ for all }0\leq i\leq n\rbrace.\end{array}$

Previous chapter: Automata over Infinite Words

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

2.3 The Büchi Acceptance Condition

The Büchi Acceptance Condition is given as a set of accepting states $F$.
A run of a Büchi automaton is accepting if some state from this set occurs infinitely often.

Infinite word

For an infinite word $\alpha$ over $\Sigma$, an Infinity Set of $\alpha$ is denoted as:
$$\text{Inf}(\alpha) = \lbrace\sigma\in\Sigma\mid\forall m\in\mathbb{N}.\exists n\in\mathbb{N}.n\geq m \text{ and } \alpha(n)=\sigma\rbrace$$

Meaning that $\text{Inf}(\alpha)$ is a set of all letters $\sigma$ from the alphabet $\Sigma$, so that
for all $m$, you can always find $\sigma$ as the n-th letter of $\alpha$ when there exists an $n$ where $n\geq m$.

This denotes the set of all letters of $\Sigma$ that occur infinitely often in $\alpha$.

Büchi Condition

Previous chapter: Büchi automata (Preliminaries)

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

2.2 Automata over Infinite Words

The operational behavior of an automaton over infinite words is very similar to automaton over finite words:

1. Start with an initial state
2. Automaton constructs a run by reading one letter of the input alphabet at a time, and
   transitioning to a successor state permitted by its transitions.

The major difference between automata over finite and infinite words is the acceptance condition.

$\textbf{Definition 2.1. } \text{ An } \textit{automaton over infinite words } \text{is a tuple }\mathcal{A} = (\Sigma,Q,I,T,Acc)\text{, where}$
$\begin{array}{l}
\hspace{1cm} \cdot \ \Sigma \text{ is a finite } \textit{alphabet} \newline
\hspace{1cm} \cdot \ Q \text{ is a finite set of } \textit{states} \newline
\hspace{1cm} \cdot \ I \subseteq Q \text{ is a subset of } \textit{initial states} \newline
\hspace{1cm} \cdot \ T \subseteq Q \times \Sigma \times Q \text{ is a set of } \textit{transitions} \text{, and} \newline
\hspace{1cm} \cdot \ Acc \subseteq Q^\omega \text{ is the } \textit{accepting condition}
\end{array}$

In the following, we refer an automaton over infinite words simply as an automaton.

Runs of Büchi automata

A run in a Büchi automaton has to transition infinitely many times, and starts with the initial state.

Previous chapter: The Logic-Automata Connection

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

2.1 Preliminaries

Basic math notations	Example
Natural numbers	$\mathbb{N} = \lbrace 0,1,2,3\dots\rbrace$
Positive Natural numbers	$\mathbb{N}^+ = \lbrace 1,2,3\dots\rbrace$
Numbers from $n$ to $m$	$[n,m] = \lbrace n,n+1,\dots,m\rbrace$ For $n,m\in \mathbb{N}$ with $n\leq m$
Numbers from $0$ to $m$	$[m] = \lbrace 0,1,\dots,m\rbrace$

$$$$

Alphabet and Letter	Example
Alphabet	a nonempty, finite set of symbols, usually denoted by $\Sigma$
Letter	elements of an alphabets, denoted by $\sigma$

$$$$

Finite and Infinite Word	Example
Finite Words	concatenation $w=w(0)w(1)\dots w(n-1)$ of finitely many letters of $\Sigma$
Infinite Words	$\alpha$ (will be explained in chapter 2.3
$n$-th letter of word $w$	$w(n)$ for each $n\in [|w| - 1]$
Length of words $w$	$|w|$
set of all finite words	\Sigma^*$
Infinite Words	$\alpha$ (will be explained in chapter 2.3
set of all non-empty finite words	$\Sigma^+ = \Sigma^* \backslash \lbrace \epsilon \rbrace$
set of all infinite words	$\Sigma^\omega$

$$$$

Language	Example
language over finite words ($\omega$-language)	each subset of $\Sigma^*$
language over infinite words ($\omega$-language)	each subset of $\Sigma^\omega$

Previous chapter: Synthesis

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Verification or Synthesis

In applications like verification and synthesis, the automata- and game-theoretic machinery is usually “hidden” behind a logical formulation of the problem.

Logics with corresponding Automata

S1S‘s expressiveness exceeds that of LTL, and
S2S‘s expressiveness exceeds that of CTL* (on binary trees)

Logic	Usage	Example
Linear-time temporal logic (LTL)	sets of infinite words	$\square \Diamond \ell_1$
Computation-tree logic (CTL / CTL*)	sets of infinite trees	$\textsf{EF}\ell_1 \wedge \textsf{EF}m_1$
Monadic second-order logic with one successor (S1S)	logic over infinite words	$\forall x . x \in P \rightarrow S(x) \in P$
Monadic second-order logic with two successors (S2S)	logic over infinite binary trees	$\forall x . x \in P \rightarrow S_1(x) \in P \vee S_2(x) \in P$

Explaination

• $\square \Diamond \ell_1$
  $P_0$ is infinitely often at location $\ell_1$.
• $\textsf{EF}\ell_1 \wedge \textsf{EF}m_1$
  There exists a computation path in which $P_0$ reaches location $\ell_1$, and
  there is a (possibly different) computation path in which $P_1$ reaches location $m_1$.
• $\forall x . x \in P \rightarrow S(x) \in P$
  A (given) set of natural numbers $P$ is either empty, or
  consists of all positions starting from some position of the word.
• $\forall x . x \in P \rightarrow S_1(x) \in P \vee S_2(x) \in P$
  A (given) set of nodes $P$ contains from each node $n \in P$ an entire path starting in $n$.