<p>The following paper:
<a href="http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf" rel="nofollow noreferrer">http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf</a>
shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup. </p>

<p>Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).</p>

CC BY-SA 4.0
2020-01-09T10:16:57.520Z
2020-01-09T10:16:57.520Z
Shaull
<p>Given two deterministic parity automata <span class="math-container">$A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$</span> and <span class="math-container">$A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$</span> with the finite set of states <span class="math-container">$Q_i$</span>, the finite alphabet <span class="math-container">$\Sigma_i$</span>, the transition function <span class="math-container">$\delta_i : Q_i \times \Sigma \rightarrow Q_i$</span>, the initial state <span class="math-container">$q_{0i}$</span> in <span class="math-container">$Q_i$</span>, and the coloring function <span class="math-container">$c_i : Q_i \rightarrow \mathbb{N}$</span>, with <span class="math-container">$i \in\{0,1\}$</span>.</p>

<p>How is the intersection of two deterministic parity automata formally defined? In particular, how are the coloring functions combined?</p>

CC BY-SA 4.0
2019-06-20T15:21:53.570Z
Hint: you can start by proving that there is no way to define a correct coloring function for the intersection on 
the states $Q_1\times Q_2$ of the product automaton.
Denis
<automata-theory><omega-language>
Intersection of two deterministic parity automata
kafka
# Intersection of two deterministic parity automata

(Asked by: username_0 on 2019-06-19)

Given two deterministic parity automata $A\_1=(Q\_1,\Sigma,\delta,q\_{01},c\_1)$ and $A\_2=(Q\_2,\Sigma,\delta,q\_{02},c\_2)$ with the finite set of states $Q\_i$, the finite alphabet $\Sigma\_i$, the transition function $\delta\_i : Q\_i \times \Sigma \rightarrow Q\_i$, the initial state $q\_{0i}$ in $Q\_i$, and the coloring function $c\_i : Q\_i \rightarrow \mathbb{N}$, with $i \in\{0,1\}$.

How is the intersection of two deterministic parity automata formally defined? In particular, how are the coloring functions combined?

**Tags:** automata-theory, omega-language
> **Comments:**
> **username_1**: Hint: you can start by proving that there is no way to define a correct coloring function for the intersection on  the states $Q_1\times Q_2$ of the product automaton.  

---

## 1 answers

### Answer by username_2 on 2020-01-09. Score: 3 | Accepted answer

The following paper:
<http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf>
shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup.

Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).


---

