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 '19 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 '19 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 '19 at 16:14

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.