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

  • $\begingroup$ 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. $\endgroup$ Commented Apr 28, 2023 at 11:12
  • $\begingroup$ 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? $\endgroup$ Commented Apr 28, 2023 at 12:02
  • $\begingroup$ Could you kindly point to a literature in which the transition-based definition is being used? $\endgroup$
    – sas
    Commented Oct 5, 2023 at 20:34
  • $\begingroup$ 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? $\endgroup$ Commented Oct 6, 2023 at 6:01
  • $\begingroup$ 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). $\endgroup$ Commented Nov 22, 2023 at 10:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.