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?

  • $\begingroup$ 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. $\endgroup$ – Denis Jun 20 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.