<p>As Emil explained in a comment:</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-02-26T16:31:04.993Z
2021-02-26T16:31:04.993Z
Yekhezkel Yovel
<p>I've been trying hard to understand something. According to <a href="https://en.wikipedia.org/wiki/%CE%A9-automaton#Acceptance_conditions" rel="nofollow noreferrer">wikipedia</a> and <a href="https://faculty.idc.ac.il/udiboker/files/RabinVsStreett.pdf" rel="nofollow noreferrer">this paper</a>, 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?</p>

CC BY-SA 4.0
2021-02-24T21:21:56.523Z
As far as I can tell, it can. Who told you otherwise?
Emil Jeřábek
CC BY-SA 4.0
2021-02-24T21:45:31.300Z
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
Yekhezkel Yovel
CC BY-SA 4.0
2021-02-24T21:48:56.620Z
For example, can I define a Rabin acceptance condition to be {<\emptyset, Q>}?
Yekhezkel Yovel
CC BY-SA 4.0
2021-02-24T22:29:48.920Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-02-25T15:20:01.963Z
@EmilJeřábek I now watched her lecture again and she defines the Rabin condition so that the left side must be visited i.o. and the right side must not, as opposed to Wikipedia and the paper I saw. So yes, she did mean that the right set should be nonempty, but she places them differently. Or could it be just an error she made during the lecture? perhaps I should ask her.
Yekhezkel Yovel
CC BY-SA 4.0
2021-02-25T15:28:44.630Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-02-26T16:33:18.307Z
@EmilJeřábek thank you very much for your informative insights. I wrote an answer based on the discussion here, but I will be very happy to accept your answer, should you write one.
Yekhezkel Yovel
<fl.formal-languages><automata-theory><omega-language>
Definition of Rabin acceptance condition for omega automatons
Yekhezkel Yovel
# Definition of Rabin acceptance condition for omega automatons

(Asked by: username_0 on 2021-02-24)

I've been trying hard to understand something. According to [wikipedia](https://en.wikipedia.org/wiki/%CE%A9-automaton#Acceptance_conditions) and [this paper](https://faculty.idc.ac.il/udiboker/files/RabinVsStreett.pdf), 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?

**Tags:** fl.formal-languages, automata-theory, omega-language
> **Comments:**
> **username_1**: As far as I can tell, it can. Who told you otherwise?  
> **username_0**: 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  
> **username_0**: For example, can I define a Rabin acceptance condition to be {<\emptyset, Q>}?  
> **username_1**: 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.  
> **username_0**: @EmilJeřábek I now watched her lecture again and she defines the Rabin condition so that the left side must be visited i.o. and the right side must not, as opposed to Wikipedia and the paper I saw. So yes, she did mean that the right set should be nonempty, but she places them differently. Or could it be just an error she made during the lecture? perhaps I should ask her.  
> **username_1**: 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.  
> **username_0**: @EmilJeřábek thank you very much for your informative insights. I wrote an answer based on the discussion here, but I will be very happy to accept your answer, should you write one.  

---

## 1 answers

### Answer by username_0 on 2021-02-26. Score: 0 | Accepted answer

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.


---

