AGV 10.3 -- Closure Properties of Muller automata Under Boolean Operations

Previous chapter: From Büchi automata to Muller automata

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

Introduction

We now show that deterministic Muller automata are closed, like nondeterministic Büchi automata, under the Boolean operations (complementation, union, and intersection).

First we introduce the construction of these automaton with operations, then we will prove they are close by the runs under those constructions.

Automata construction of Complementation

$\textbf{Construction 10.3. } \text{Let }\mathcal{A} = (\Sigma,Q,I,T,\small\text{MULLER} \normalsize (\mathcal{F}))\text{ be a complete and deterministic Muller}\newline\text{automaton, where we assume w.l.o.g that }Q\neq\varnothing.\text{ We construct the deterministic Muller}\newline\text{automaton }\mathcal{A}^C = (\Sigma,Q,I,T,\small\text{MULLER} \normalsize(2^Q\setminus\mathcal{F}))\text{ with }\mathcal{L(A^C)}=\Sigma\setminus\mathcal{L(A)}.$

Automata construction of Intersection

We use the function $pr_n$ for $n\in\mathbb{N}$ to project to the (n+1)th component of a arbitrary length tuple, for example:

• $pr_0(x, y)=x$
• $pr_1(x, y)=y$
• $pr_2(x, y),pr_3(x, y),\dots pr_n(x, y) =\text{Undefined}$

We can also apply the projection to a set and return a set of components: $pr_n(S) = \bigcup_{s∈S}{pr_n(s)}.$

$\textbf{Construction 10.4. } \text{For Muller automata }\mathcal{A_1} = (\Sigma,Q,I,T,\small\text{MULLER} \normalsize (\mathcal{F_1}))\text{ and}\newline\mathcal{A_2} = (\Sigma,Q,I,T,\small\text{MULLER} \normalsize (\mathcal{F_2}))\text{ over the same alphabet }\Sigma.\text{ We construct the Muller Automaton}\newline\mathcal{A}_\cap = (\Sigma,Q_1\times Q_2,I_1\times I_2,T_\cap,\small\text{MULLER} \normalsize(\mathcal{F_\cap}))\text{ with }\mathcal{L(A_\cap)}=\mathcal{L(A_1)}\cap\mathcal{L(A_2)}\text{ and where }\mathcal{A_\cap}\text{ is}\newline\text{deterministic if }\mathcal{A_1}\text{ and }\mathcal{A_2}\text{ are deterministic, as follows:}$

$\begin{array}{l}\hspace{1cm}\cdot \ T_\cap=\lbrace((q_1,q_2),\sigma,(q’_1,q’_2))\mid(q_1,\sigma,q’_1)\in T_1,(q_2,\sigma,q’_2)\in T_2\rbrace\newline\hspace{1cm}\cdot \ \mathcal{F}_\cap = \lbrace P\subseteq Q_1\times Q_2\mid pr_0(P)\in\mathcal{F_1},pr_1(P)\in\mathcal{F_2}\rbrace\end{array}$

Closure Properties of under Boolean Operations

$\textbf{Theorem 10.3. } \textit{The languages recognizable by deterministic Muller automata are closed}\newline\textit{under Boolean operations (complementation, union, intersection).}.$

Proof of Deterministic Muller automata are closed under complementation

For a deterministic Muller automaton $\mathcal{A}$, the automaton $\mathcal{A’}$ of Construction 10.3 recognizes the complement language, because any set $F\notin F$ has to be in the complement, i.e., $F\in2^Q\setminus F$.

Proof of Deterministic Muller automata are closed under Intersection

For deterministic Muller automata $\mathcal{A_1}$ and $\mathcal{A_2}$, the automaton $\mathcal{A}_\cap$ of Construction 10.4 recognizes the intersection. Let $r_1 = q^1_0q^1_1\dots$ and $r_2 = q^2_0q^2_1\dots$ be accepting runs of $\mathcal{A_1}$ and $\mathcal{A_2}$ on some $\alpha$. Then $r=(r^1_0,r^2_0)(r^1_1,r^2_1)\dots$ is an accepting run of $\mathcal{A}_\cap$ on $\alpha$ and vice versa.

Proof of Deterministic Muller automata are closed under Union

It can be proved by De Morgan’s laws if they are closed under complement and intersection:

$$\Sigma\setminus(\mathcal{L(A_1)}\cap\mathcal{L(A_2)})=(\Sigma\setminus\mathcal{L(A_1)})\cup(\Sigma\setminus\mathcal{L(A_2)})$$

Regular language and Limit operator

Similar to Büchi automata in section 4.1, we can define an $\omega$-regular language from regular language, which is recognizable by deterministic Muller Automata:

$\textbf{Theorem 10.4. }\textit{An language }L\textit{ is recognizable by a deterministic Muller Automata if and only}\newline\textit{if }L\textit{ is a Boolean combination of langauges }\overrightarrow{W}\textit{ where }W\subseteq\Sigma^*\text{ is regular.}$

Proof

$”\Leftarrow”$
If $W$ is regular, then $\overrightarrow{W}$ is recognizable by a deterministic Büchi automaton. Hence, $\overrightarrow{W}$ is recognizable by a deterministic Muller automaton. Thus, the boolean combination $\mathcal{L}$ is recognizable by a deterministic Muller automaton.

$”\Rightarrow”$
A deterministic Muller automaton $\mathcal{A}$ accepts some word $\alpha$ with a unique run $r$ if for some $F\in\mathcal{F}$ we have that $\text{Inf}(r)=F$. Thus, there is some $F\in\mathcal{F}$ such that for all $q\in F$ we have that $\alpha\in\overrightarrow{W_q}$ and for all $q\notin F$ we have that $\alpha\notin\overrightarrow{W_q}$, where $\overrightarrow{W_q}=\mathcal{L(A_q)}$ for the finite-word automaton $\mathcal{A}_q=(\Sigma,Q,I,T,\lbrace q\rbrace)$. Hence,

$$\alpha\in\underset{F\in\mathcal{F}}{\bigcup}\left(\underset{q\in F}{\bigcap}\overrightarrow{W_q}\cap\underset{q\notin F}{\bigcap}(\Sigma^\omega\setminus\overrightarrow{W_q})\right)$$

---

Next chapter: Semi-Deterministic Büchi Automata

Further Reading: De Morgan’s laws