2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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

0

Reset to default

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.