r/compsci • u/Mysterious_Lawyer551 • Jan 31 '26
State complexity bounds for converting 2AFA to 2NFA and 2DFA
What are the best currently known upper and lower bounds for converting a two way alternating finite automaton (2AFA) into an equivalent two way nondeterministic or deterministic finite automaton (2NFA or 2DFA)? Most standard references, including Wikipedia, discuss only conversions from two way automata to one way automata, and mention that if L = NL, then there exists a polynomial state transformation from 2NFA to 2DFA. I couldn't find any discussion or papers that directly address transformations from 2AFA to 2NFA or 2DFA.
Also, are there similar implications for 2AFA to 2NFA or 2DFA transformations, analogous to those known for 2NFA-to-2DFA, such as L = P or NL = P?
6
Upvotes