<p>Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.</p>
<p><em>Alternating finite automata</em> (AFA) are usually defined in modern literature in the following terms. An AFA is a tuple <span class="math-container">$A=(\Sigma,Q,q_0,\delta,F)$</span> for an alphabet <span class="math-container">$\Sigma$</span>, a set of states <span class="math-container">$Q$</span>, an initial state <span class="math-container">$q_0$</span>, a set of final states <span class="math-container">$F\subseteq Q$</span>, and a transition function <span class="math-container">$\delta:Q\times\Sigma\to\mathcal{B}^+(Q)$</span>, where <span class="math-container">$\mathcal{B}^+(Q)$</span> is the set of <em>positive Boolean formulas</em> over <span class="math-container">$Q$</span>.</p>
<p>The semantics is well-known. For example, if <span class="math-container">$\delta(q,a)=q_1\land(q_2\lor q_3)$</span> and the automaton reads <span class="math-container">$a$</span> from <span class="math-container">$q$</span>, then the rest of the word must be accepted both from <span class="math-container">$q_1$</span> and either <span class="math-container">$q_2$</span> or <span class="math-container">$q_3$</span>.</p>
<p>However, older literature (and <a href="https://en.wikipedia.org/wiki/Alternating_finite_automaton" rel="nofollow noreferrer">Wikipedia</a>, btw), often uses a different definition, where an AFA is a tuple <span class="math-container">$A=(\Sigma,Q,q_0,\Delta,F)$</span> where <span class="math-container">$Q$</span> is partitioned into the <em>universal</em> states <span class="math-container">$Q_\forall$</span>, and the <em>existential</em> states <span class="math-container">$Q_\exists$</span>, and <span class="math-container">$\Delta\subseteq Q\times\Sigma\times Q$</span> is a common transition relation. The semantics here is that a word <span class="math-container">$a\cdot w$</span> is accepted on an existential state <span class="math-container">$q\in Q_\exists$</span> if <em>there is</em> a state <span class="math-container">$q'$</span> such that <span class="math-container">$\Delta(q,a,q')$</span> and <span class="math-container">$w$</span> is accepted from <span class="math-container">$q'$</span>, while <span class="math-container">$a\cdot w$</span> is accepted on a universal state <span class="math-container">$q\in Q_\forall$</span> if <em>for all</em> states <span class="math-container">$q'$</span> such that <span class="math-container">$\Delta(q,a,q')$</span>, <span class="math-container">$w$</span> is accepted from <span class="math-container">$q'$</span>.</p>
<p>Let's call the first AFAs &quot;transition-based&quot; and the second ones &quot;state-based&quot;. It's clear that a state-based AFA leads directly to a transition-based AFA. What is less clear to me is how to take a transition-based AFA and turn it into a state-based one.
The only way I can see is by using <span class="math-container">$\epsilon$</span>-transitions, with additional states for each subformula of <span class="math-container">$\delta(q,a)$</span>, but <span class="math-container">$\epsilon$</span>-transitions are problematic since I don't see a general way to remove them from state-based AFAs (is it possible, btw?).</p>
<p>So how does one go from transition-based AFAs to state-based AFAs?</p>
<p><strong>Edit:</strong> I'm talking about a polynomial translation, without determinizing to a DFA first (which is trivially a state-based AFA as Emil mentioned in the comments).</p>

CC BY-SA 4.0
2023-04-28T11:12:40.427Z
I don’t see a direct way other than by using $\epsilon$-transitions, as you described. Ultimately, all these models are equivalent to DFA, so if you don’t want $\epsilon$-transitions, convert the automaton to an equivalent DFA, which also functions trivially as a state-based AFA.
Emil Jeřábek
CC BY-SA 4.0
2023-04-28T12:02:39.067Z
Thanks! I've edited the question. As you may have guessed, I was talking about a polynomial translation. Afaik the original definition (Chandra Kozen Stockmayer) is the state-based one. Then the literature started to use the transition-based one. Who was the first who came up with the latter?
Nicola Gigante
CC BY-SA 4.0
2023-10-05T20:34:45.433Z
Could you kindly point to a literature in which the transition-based definition is being used?
sas
CC BY-SA 4.0
2023-10-06T06:01:44.933Z
Any modern resource that I found, see *e.g.* https://dl.acm.org/doi/pdf/10.1145/377978.377993 instead do you know of any modern resource that uses the state-based definition?
Nicola Gigante
CC BY-SA 4.0
2023-11-22T10:56:41.347Z
Actually, Chandra, Kozen, and Stockmayer (https://dl.acm.org/doi/10.1145/322234.322243 , p. 127) use the transition-based definition, even allowing *arbitrary* Boolean functions. Also, note that the Wikipedia definition does explicitly allow $\epsilon$-transitions (though I wonder whether it would be better to rewrite the article).
Emil Jeřábek
CC BY-SA 4.0
2023-11-22T11:50:10.517Z
FWIW, I rewrote the definition on Wikipedia now to use the transition-based definition.
Emil Jeřábek
CC BY-SA 4.0
2023-11-23T00:11:53.000Z
Thanks, that will avoid further confusion!
Nicola Gigante
<automata-theory><alternation>
State-based vs. transition-based definitions of alternating automata
Nicola Gigante
# State-based vs. transition-based definitions of alternating automata

(Asked by: username_0 on 2023-04-28)

Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.

*Alternating finite automata* (AFA) are usually defined in modern literature in the following terms. An AFA is a tuple $A=(\Sigma,Q,q\_0,\delta,F)$ for an alphabet $\Sigma$, a set of states $Q$, an initial state $q\_0$, a set of final states $F\subseteq Q$, and a transition function $\delta:Q\times\Sigma\to\mathcal{B}^+(Q)$, where $\mathcal{B}^+(Q)$ is the set of *positive Boolean formulas* over $Q$.

The semantics is well-known. For example, if $\delta(q,a)=q\_1\land(q\_2\lor q\_3)$ and the automaton reads $a$ from $q$, then the rest of the word must be accepted both from $q\_1$ and either $q\_2$ or $q\_3$.

However, older literature (and [Wikipedia](https://en.wikipedia.org/wiki/Alternating_finite_automaton), btw), often uses a different definition, where an AFA is a tuple $A=(\Sigma,Q,q\_0,\Delta,F)$ where $Q$ is partitioned into the *universal* states $Q\_\forall$, and the *existential* states $Q\_\exists$, and $\Delta\subseteq Q\times\Sigma\times Q$ is a common transition relation. The semantics here is that a word $a\cdot w$ is accepted on an existential state $q\in Q\_\exists$ if *there is* a state $q'$ such that $\Delta(q,a,q')$ and $w$ is accepted from $q'$, while $a\cdot w$ is accepted on a universal state $q\in Q\_\forall$ if *for all* states $q'$ such that $\Delta(q,a,q')$, $w$ is accepted from $q'$.

Let's call the first AFAs "transition-based" and the second ones "state-based". It's clear that a state-based AFA leads directly to a transition-based AFA. What is less clear to me is how to take a transition-based AFA and turn it into a state-based one.
The only way I can see is by using $\epsilon$-transitions, with additional states for each subformula of $\delta(q,a)$, but $\epsilon$-transitions are problematic since I don't see a general way to remove them from state-based AFAs (is it possible, btw?).

So how does one go from transition-based AFAs to state-based AFAs?

**Edit:** I'm talking about a polynomial translation, without determinizing to a DFA first (which is trivially a state-based AFA as Emil mentioned in the comments).

**Tags:** automata-theory, alternation
> **Comments:**
> **username_1**: I don’t see a direct way other than by using $\epsilon$-transitions, as you described. Ultimately, all these models are equivalent to DFA, so if you don’t want $\epsilon$-transitions, convert the automaton to an equivalent DFA, which also functions trivially as a state-based AFA.  
> **username_0**: Thanks! I've edited the question. As you may have guessed, I was talking about a polynomial translation. Afaik the original definition (Chandra Kozen Stockmayer) is the state-based one. Then the literature started to use the transition-based one. Who was the first who came up with the latter?  
> **username_2**: Could you kindly point to a literature in which the transition-based definition is being used?  
> **username_0**: Any modern resource that I found, see *e.g.* https://dl.acm.org/doi/pdf/10.1145/377978.377993 instead do you know of any modern resource that uses the state-based definition?  
> **username_1**: Actually, Chandra, Kozen, and Stockmayer (https://dl.acm.org/doi/10.1145/322234.322243 , p. 127) use the transition-based definition, even allowing *arbitrary* Boolean functions. Also, note that the Wikipedia definition does explicitly allow $\epsilon$-transitions (though I wonder whether it would be better to rewrite the article).  
> **username_1**: FWIW, I rewrote the definition on Wikipedia now to use the transition-based definition.  
> **username_0**: Thanks, that will avoid further confusion!  

---

## 0 answers

