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$ Have you read topological extension of parity automata by Michał Skrzypczak? $\endgroup$
    – John L.
    Jun 21, 2019 at 0:22
  • 1
    $\begingroup$ I think that this is a good question, as I am not aware of any concise write-up of a construction to do so. In principle, one could treat the parity automata as deterministic Rabin automata, build the straight-forward intersection, and then apply the DRA->DPA construction from ArXiV/CoRR paper 1701.05738 that bases on index appearance records. But that is quite a detour, and a direction construction should be given in some textbook. $\endgroup$
    – DCTLib
    Jun 21, 2019 at 14:21
  • $\begingroup$ Yes, indeed that is my question, if there is a direct contruction of the intersection of two DPA in literature. Do you have any reference to the one for two deterministic rabin automaton? $\endgroup$
    – kafka
    Jun 21, 2019 at 16:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.