What it the easiest way to decide whether or not a given non deterministic Büchi automaton is equivalent to some deterministic Büchi automaton? In other words, how can we decide whether a Buchi automaton is "semantically deterministic"?
I am aware that I could solve the problem using the following procedures:
- Convert the Buchi automaton into a Muller determistic one (for example using Safra construction) and then checking whether the obtained DMA is closed under superloops.
- Use the condition given in the book Infinite Wors by D. Perrin and J.-E. Pin using $\omega$-semigroups. That is, $\forall f \in S$ such that $f<e$, $(s,f)$ and $(s,e)$ are a linked pair such that $se^{\omega} \in \phi(L)$, check whether or not $sf^{\omega}$ also belong to $\phi(L)$.
However I wonder if there exist others ways to achive the goal.
Thank you in advance.
Let $A$ be a finite alphabet. For a regular $\omega$-language $L$ the following are equivalent:
i) $L$ is recognizable by a finite Büchi automaton,
ii) $L = \{ \xi \in A^{\omega} : \xi \mbox{ has infinitely many prefixes in } W \}$ for some regular language $W$,
iii) $L$ is a countable intersection of open sets (i.e. a $G_{\delta}$-set) in the product topology on $A^{\omega}$.
The proofs of these facts could be found in the book you mentioned. Also in the book the following equivalences are proven:
1) $L \subseteq A^{\omega}$ is closed and recognizable,
2) if $L$ is recognized by a finite Büchi automaton, then it is also recognized by the same Büchi automaton, but with the set of non-trap states as final states, where a state is a non-trap state if some final state is reachable.
Using this at least for the closed sets, which in $A^{\omega}$ are also $G_{\delta}$-sets, your problem could be solved for this subclass of deterministically acceptable Büchi languages. Given your (possibly) non-deterministic Büchi automaton, switch the final states as written in condition 2) above, and if both accept the same language then your language is closed, hence deterministically acceptable. Checking if two Büchi-automata accept the same language is simple, just check that the labeling of every accepting loop is also the labeling of some accepting loop in the other automaton (i.e. using that two regular $\omega$-languages are the same if their set of ultimately periodic words coincide).
I do not know any algorithm that starts directly from the non-deterministic Büchi automaton in general without using Muller automata or $\omega$-semigroups. But I try to give you some directions where to look. As written above your question has some topological flavor, and one of the first papers which asked for algorithms computing the topological complexity (i.e. the Borel class) is L.H. Landweber: Decision problems for $\omega$-automata, but here in his algorithms he also starts from a Muller automata. A further refinement of the Borel hierarchy is the so called Wadge-Wagner-hierarchy of regular languages. Here the regular $\omega$-languages are classified up to continuous reducibility (i.e. continuous inverse images) and this refines the Borel hierachy. Hence algorithms for computing the Wagner class solve also your problem. For a given Muller automaton or $\omega$-semigroups the Wagner-class of a given regular $\omega$-language is easy to compute. You can find a description also in the mentioned book. I find the original article on the Wagner hierarchy quite difficult to read (see also my post here), another reference for computing the Wagner classes is:
Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time Thomas Wilke, Haiseung Yoo, TAPSOFT '95, see here.
Hope this helps!