<p>It turns out the answer is no, some counter-examples can be found in <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf" rel="nofollow noreferrer">this paper</a>.</p>
<p>Also here is a <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGness.pdf" rel="nofollow noreferrer">more recent work</a> showing that such Büchi automata can be recognized in polynomial time.</p>

CC BY-SA 3.0
2012-05-28T15:14:06.183Z
thx for update, but vague! what team? did they publish? plan to? how did you hear? how did they find it? is there a reason they were looking for it? is this a theoretical curiosity or connected to some bigger problem or application? etc
vzn
CC BY-SA 3.0
2017-03-14T22:47:47.493Z
see this answer for more details: http://cstheory.stackexchange.com/a/24918/8953
Denis
CC BY-SA 4.0
2012-05-24T13:16:31.050Z
2020-11-02T11:52:22.493Z
2020-11-02T11:52:22.493Z
Denis
<p>As you pointed out, non-deterministic and deterministic Buchi automata accept different languages. The most famous 'determinization' for a Buchi automaton is given by Safra (search "Safra's construction" on web. Here's one document that comes up: www.cs.cornell.edu/courses/cs686/2003sp/Handouts/safra.pdf). The procedure is quite intricate and involves transforming given Buchi automaton into a deterministic Rabin automaton (having 'accepting' F states and 'rejecting' G states: \sigma has only finitely many states in G). Safra's construction involves much more than simply removing transitions and/or usual subset construction. </p>

CC BY-SA 3.0
2012-05-15T17:40:57.753Z
I know this, the question is about a special class of Büchi automata, namely the one that admit acceptance strategies $\sigma$. I already showed that this class has same power than the class of deterministic Büchi automata, and I described a simplified determinization procedure (in the "what is known" section). The conjecture is that there is a much simpler determinization procedure for this class, which consists just in removing some transitions.
Denis
CC BY-SA 3.0
2012-05-15T17:20:09.213Z
2012-05-15T17:20:09.213Z
Sudeep
<h2>The problem</h2>
<p>Let <span class="math-container">$A=\langle \Sigma, Q, q_0,F,\Delta\rangle$</span> be a Büchi automaton, recognizing a language <span class="math-container">$L\subseteq\Sigma^\omega$</span>.
We assume that <span class="math-container">$A$</span> has an acceptance strategy in the following sense : there is a function <span class="math-container">$\sigma:\Sigma^*\to Q$</span> which can be used to pilot runs of <span class="math-container">$A$</span>. We formalize this by the following conditions :</p>
<ul>
<li><p><span class="math-container">$\sigma(\epsilon)=q_0$</span></p>
</li>
<li><p>for all <span class="math-container">$u\in\Sigma^*$</span> and <span class="math-container">$a\in\Sigma$</span>, <span class="math-container">$(\sigma(u),a,\sigma(ua))\in\Delta$</span></p>
</li>
<li><p>for all <span class="math-container">$w=a_0a_1a_2\dots\in L$</span>, the run piloted by <span class="math-container">$\sigma$</span> is accepting, i.e. the sequence <span class="math-container">$\sigma(\epsilon),\sigma(a_0),\sigma(a_0a_1),\sigma(a_0a_1a_2),\dots$</span> has infinitely many elements in <span class="math-container">$F$</span>.</p>
</li>
</ul>
<p>To subsume the conditions, <span class="math-container">$A$</span> can accept any word of its language without having to guess anything about the future.</p>
<p>Then, under these assumptions on <span class="math-container">$A$</span>, is it true that <span class="math-container">$A$</span> can be determinized just by removing transitions ? In other words, can we always choose the next transition depending only on the current state and letter ? Is there any reference on the subject ? The same question can then be asked on co-Büchi automata, and more generally on parity automata.</p>
<h2>What is known</h2>
<p>Here are some partial results.</p>
<p>First, we can restrict <span class="math-container">$\sigma$</span> to nondeterminstic choices between states having the same residual. Indeed, if <span class="math-container">$L(q)$</span> is the language accepted from <span class="math-container">$q$</span>, an accepting strategy cannot choose <span class="math-container">$q_1$</span> over <span class="math-container">$q_2$</span> at some point, if there is <span class="math-container">$w\in L(q_2)\setminus L(q_1)$</span>.</p>
<p>Notice that the remaining choices do matter, so despite the intuition, this is not enough to get rid of the nondeterminism. This is because it is possible to stay ad infinitum in a good residual (i.e. the remaining of the word is in the residual), but reject the word because not infinitely many Büchi states are seen. This is the main difficulty of the problem : an infinite run can be wrong, without making any fatal mistake at some point.</p>
<p>Second, the problem is solved if <span class="math-container">$L=\Sigma^\omega$</span>, i.e. all words are accepted by <span class="math-container">$A$</span>. In this case, we can view <span class="math-container">$A$</span> as a Büchi game where Player I chooses input letters and Player II chooses transitions. Then we can use positional determinacy of Büchi games to extract a positional strategy for Player II. This arguments even works in the more general case of parity automata. The difficulty of this problem comes from the fact that some words are not in <span class="math-container">$L$</span>, and in this case the strategy <span class="math-container">$\sigma$</span> can have any behaviour.</p>
<p>Third, here is a proof that under the assumptions, the language <span class="math-container">$L$</span> is in the class of deterministic Büchi languages, witnessed by an automaton with states <span class="math-container">$2^Q$</span>.
Notice that this implies that <span class="math-container">$L$</span> cannot be any <span class="math-container">$\omega$</span>-regular language, for instance  if <span class="math-container">$L=(a+b)^*a^\omega$</span>, no strategy <span class="math-container">$\sigma$</span> matching the conditions can exist.</p>
<p>We start by restricting the transitions according to the first remark : the only choices we can make do not impact on the residual language. We only take successors with the maximum residual, they must exist because <span class="math-container">$\sigma$</span> exists.</p>
<p>Then, we build <span class="math-container">$A'=\langle \Sigma, 2^Q, \{ q_0\},F',\Delta'\rangle$</span> in the following way. <span class="math-container">$A'$</span> is the subset automaton of <span class="math-container">$A$</span>, but every time a Büchi state <span class="math-container">$q$</span> appears in the component, all other states can be removed from the component, and we start again from the singleton <span class="math-container">$\{ q\}$</span>. Then we can set <span class="math-container">$F'=\{\{ q\} : q\in F\}$</span>. We can verify that <span class="math-container">$A'$</span> is a deterministic Büchi automaton for <span class="math-container">$L$</span>.</p>
<p>Finally, by putting together the second and the third remarks, we can always obtain a finite memory-strategy <span class="math-container">$\sigma$</span>, by using a positional strategy for Player II in the game <span class="math-container">$A\times A'$</span> where Player I chooses letters, Player II chooses transitions in <span class="math-container">$A$</span> and wins if <span class="math-container">$A$</span> accepts whenever <span class="math-container">$A'$</span> accepts.</p>

CC BY-SA 3.0
2012-05-09T15:01:32.153Z
Write $A_\sigma$ for the (deterministic) automaton with transitions removed.  Let $w=w_0w_1\cdots$ be a word in $L$.  Then by your conditions $\sigma(w_0)\sigma(w_0w_1)\cdots$ is a run of $A_\sigma$ and is accepting, thus $L\subseteq L(A_\sigma)$.  Conversely, any accepting run of $A_\sigma$ is in particular an accepting run of $A$, thus $L(A_\sigma)\subseteq L$.
Sylvain
CC BY-SA 3.0
2012-05-09T15:02:42.457Z
@Sylvain: Which transitions are removed?
Dave Clarke
CC BY-SA 3.0
2012-05-09T15:06:12.737Z
I'm assuming you call $A_\sigma$ the automaton $A$ restricted to transitions used in the strategy $\sigma$. The problem is you don't have any guarantee that $A_\sigma$ is deterministic. For instance assume $\sigma(a)=\sigma(\epsilon)=q_0$ and $\sigma(aa)=q_1$, then $A_\sigma$ is not deterministic.
Denis
CC BY-SA 3.0
2012-05-15T14:51:28.660Z
I'm also posting it on mathOverflow, with more details on the previous work here: http://mathoverflow.net/questions/97007/buchi-automata-with-acceptance-strategy, is it ok ?
Denis
CC BY-SA 3.0
2012-05-15T19:19:38.510Z
Generally cross posting is not allowed, unless one has not received an answer after a sufficient amount of time. Given that there is an open bounty on this question, I would wait a few days. You can delete the other posting and open it in a few days. (Also, the other posting should link to this one.)
Dave Clarke
CC BY-SA 3.0
2012-05-24T16:27:00.890Z
I don't think so, this problem becomes difficult because of the infinitary condition. Indeed this problem is solved on finite words. The complexity is polynomial, both for deciding if the automaton has this special form, and for finding a good strategy. But it is possible that in spite of this, there is a reformulation in terms of FSM (so on finite words).
Denis
CC BY-SA 3.0
2012-05-29T14:48:02.657Z
you say analogous problem is solved on finite words. if you have further info or ref handy would be curious.
vzn
CC BY-SA 3.0
2012-05-30T10:54:07.090Z
on finite words, you can design a game where both players move tokens on the automaton $A$, and as before if Adam accepts then Eve has to accept. You can then show that Eve can always play as if Adam's token is at the place that hers, this gives a memoryless strategy.
Denis
<fl.formal-languages><automata-theory><regular-language><nondeterminism><omega-language>
Büchi automata with acceptance strategy
Denis
# Büchi automata with acceptance strategy

(Asked by: username_0 on 2012-05-09)

## The problem

Let $A=\langle \Sigma, Q, q\_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense : there is a function $\sigma:\Sigma^\*\to Q$ which can be used to pilot runs of $A$. We formalize this by the following conditions :

* $\sigma(\epsilon)=q\_0$
* for all $u\in\Sigma^\*$ and $a\in\Sigma$, $(\sigma(u),a,\sigma(ua))\in\Delta$
* for all $w=a\_0a\_1a\_2\dots\in L$, the run piloted by $\sigma$ is accepting, i.e. the sequence $\sigma(\epsilon),\sigma(a\_0),\sigma(a\_0a\_1),\sigma(a\_0a\_1a\_2),\dots$ has infinitely many elements in $F$.

To subsume the conditions, $A$ can accept any word of its language without having to guess anything about the future.

Then, under these assumptions on $A$, is it true that $A$ can be determinized just by removing transitions ? In other words, can we always choose the next transition depending only on the current state and letter ? Is there any reference on the subject ? The same question can then be asked on co-Büchi automata, and more generally on parity automata.

## What is known

Here are some partial results.

First, we can restrict $\sigma$ to nondeterminstic choices between states having the same residual. Indeed, if $L(q)$ is the language accepted from $q$, an accepting strategy cannot choose $q\_1$ over $q\_2$ at some point, if there is $w\in L(q\_2)\setminus L(q\_1)$.

Notice that the remaining choices do matter, so despite the intuition, this is not enough to get rid of the nondeterminism. This is because it is possible to stay ad infinitum in a good residual (i.e. the remaining of the word is in the residual), but reject the word because not infinitely many Büchi states are seen. This is the main difficulty of the problem : an infinite run can be wrong, without making any fatal mistake at some point.

Second, the problem is solved if $L=\Sigma^\omega$, i.e. all words are accepted by $A$. In this case, we can view $A$ as a Büchi game where Player I chooses input letters and Player II chooses transitions. Then we can use positional determinacy of Büchi games to extract a positional strategy for Player II. This arguments even works in the more general case of parity automata. The difficulty of this problem comes from the fact that some words are not in $L$, and in this case the strategy $\sigma$ can have any behaviour.

Third, here is a proof that under the assumptions, the language $L$ is in the class of deterministic Büchi languages, witnessed by an automaton with states $2^Q$.
Notice that this implies that $L$ cannot be any $\omega$-regular language, for instance if $L=(a+b)^\*a^\omega$, no strategy $\sigma$ matching the conditions can exist.

We start by restricting the transitions according to the first remark : the only choices we can make do not impact on the residual language. We only take successors with the maximum residual, they must exist because $\sigma$ exists.

Then, we build $A'=\langle \Sigma, 2^Q, \{ q\_0\},F',\Delta'\rangle$ in the following way. $A'$ is the subset automaton of $A$, but every time a Büchi state $q$ appears in the component, all other states can be removed from the component, and we start again from the singleton $\{ q\}$. Then we can set $F'=\{\{ q\} : q\in F\}$. We can verify that $A'$ is a deterministic Büchi automaton for $L$.

Finally, by putting together the second and the third remarks, we can always obtain a finite memory-strategy $\sigma$, by using a positional strategy for Player II in the game $A\times A'$ where Player I chooses letters, Player II chooses transitions in $A$ and wins if $A$ accepts whenever $A'$ accepts.

**Tags:** fl.formal-languages, automata-theory, regular-language, nondeterminism, omega-language

> **Comments:**
> **username_1**: Write $A_\sigma$ for the (deterministic) automaton with transitions removed.  Let $w=w_0w_1\cdots$ be a word in $L$.  Then by your conditions $\sigma(w_0)\sigma(w_0w_1)\cdots$ is a run of $A_\sigma$ and is accepting, thus $L\subseteq L(A_\sigma)$.  Conversely, any accepting run of $A_\sigma$ is in particular an accepting run of $A$, thus $L(A_\sigma)\subseteq L$.  
> **username_2**: @username_1: Which transitions are removed?  
> **username_0**: I'm assuming you call $A_\sigma$ the automaton $A$ restricted to transitions used in the strategy $\sigma$. The problem is you don't have any guarantee that $A_\sigma$ is deterministic. For instance assume $\sigma(a)=\sigma(\epsilon)=q_0$ and $\sigma(aa)=q_1$, then $A_\sigma$ is not deterministic.  
> **username_0**: I'm also posting it on mathOverflow, with more details on the previous work here: http://mathoverflow.net/questions/97007/buchi-automata-with-acceptance-strategy, is it ok ?  
> **username_2**: Generally cross posting is not allowed, unless one has not received an answer after a sufficient amount of time. Given that there is an open bounty on this question, I would wait a few days. You can delete the other posting and open it in a few days. (Also, the other posting should link to this one.)  
> **username_0**: I don't think so, this problem becomes difficult because of the infinitary condition. Indeed this problem is solved on finite words. The complexity is polynomial, both for deciding if the automaton has this special form, and for finding a good strategy. But it is possible that in spite of this, there is a reformulation in terms of FSM (so on finite words).  
> **username_3**: you say analogous problem is solved on finite words. if you have further info or ref handy would be curious.  
> **username_0**: on finite words, you can design a game where both players move tokens on the automaton $A$, and as before if Adam accepts then Eve has to accept. You can then show that Eve can always play as if Adam's token is at the place that hers, this gives a memoryless strategy.  

---

## 2 answers

### Answer by username_0 on 2012-05-24. Score: 4 | Accepted answer

It turns out the answer is no, some counter-examples can be found in [this paper](http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf).

Also here is a [more recent work](http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGness.pdf) showing that such Büchi automata can be recognized in polynomial time.

> **Comments:**
> **username_3**: thx for update, but vague! what team? did they publish? plan to? how did you hear? how did they find it? is there a reason they were looking for it? is this a theoretical curiosity or connected to some bigger problem or application? etc  
> **username_0**: see this answer for more details: http://cstheory.stackexchange.com/a/24918/8953  

---

### Answer by username_4 on 2012-05-15. Score: -2

As you pointed out, non-deterministic and deterministic Buchi automata accept different languages. The most famous 'determinization' for a Buchi automaton is given by Safra (search "Safra's construction" on web. Here's one document that comes up: www.cs.cornell.edu/courses/cs686/2003sp/Handouts/safra.pdf). The procedure is quite intricate and involves transforming given Buchi automaton into a deterministic Rabin automaton (having 'accepting' F states and 'rejecting' G states: \sigma has only finitely many states in G). Safra's construction involves much more than simply removing transitions and/or usual subset construction.

> **Comments:**
> **username_0**: I know this, the question is about a special class of Büchi automata, namely the one that admit acceptance strategies $\sigma$. I already showed that this class has same power than the class of deterministic Büchi automata, and I described a simplified determinization procedure (in the "what is known" section). The conjecture is that there is a much simpler determinization procedure for this class, which consists just in removing some transitions.  

---

