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)$$
Further Reading: De Morgan’s laws
Please cite the source for reprints, feel free to verify the sources cited in the article, and point out any errors or lack of clarity of expression. You can comment in the comments section below or email to GreenMeeple@yahoo.com