# State-based vs. transition-based definitions of alternating automata

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, 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).

• 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. Commented Apr 28, 2023 at 11:12
• 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? Commented Apr 28, 2023 at 12:02
• Could you kindly point to a literature in which the transition-based definition is being used?
– sas
Commented Oct 5, 2023 at 20:34
• Any modern resource that I found, see e.g. dl.acm.org/doi/pdf/10.1145/377978.377993 instead do you know of any modern resource that uses the state-based definition? Commented Oct 6, 2023 at 6:01
• Actually, Chandra, Kozen, and Stockmayer (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). Commented Nov 22, 2023 at 10:56