I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left set in a pair must not be empty, but I cannot figure out why. Since the condition requires that at least one of the pairs will have none of the states on the left being visited infinitely often, and at least one of the state on the right be visited infinitely often, an empty left set seems to mean just that for every pair in the condition it is true that none of it's states is being visited infinitely often. So my question is: why can't the left side of the pair be empty?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ As far as I can tell, it can. Who told you otherwise? $\endgroup$– Emil JeřábekFeb 24, 2021 at 21:21
-
$\begingroup$ A proffesor from the Hebrew University told me that a rule <\emptyset,F> cannot exist in a Rabin acceptance condition... but I am very new to the subject of omega-automata and I may have misunderstood... @EmilJeřábek $\endgroup$– Yekhezkel YovelFeb 24, 2021 at 21:45
-
$\begingroup$ For example, can I define a Rabin acceptance condition to be {<\emptyset, Q>}? $\endgroup$– Yekhezkel YovelFeb 24, 2021 at 21:48
-
1$\begingroup$ Yes, why not. (The automaton will accept all $\omega$-words for which there exists an infinite run.) Could it be perhaps that your professor meant that the right set in each pair should be nonempty? While this is not really necessary to impose either, pairs with empty set on the right are redundant, as they can never match. $\endgroup$– Emil JeřábekFeb 24, 2021 at 22:29
-
1$\begingroup$ All right, that makes sense. I honestly do not know how standardized are the conventions which set is left and which is right here, as this is not really my field, but certainly they are just that: conventions. It is of no mathematical consequence whether you define it one way or the other, so your professor can do whatever she prefers. $\endgroup$– Emil JeřábekFeb 25, 2021 at 15:28
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
As Emil explained in a comment:
The sides are interchangable when defining the Rabin condition - my professor defined the left side as the one that is required to be visited infinitely often while Wikipedia and the paper I've mentioned define the right side as the one that is required to be visited infinitely often.
Whichever the side that has to be visited infinitely often is, it can be required to be non-empty, since if it is empty, the pair is meaningless - it cannot be visited infinitely often.
It is okay not to require it to be non-empty, because if it is empty, the pair simply accepts the empty language without causing any contradiction or changing any of the desired results of the definition.