For each two-way alternating finite automaton (2AFA) A with s states, we directly build a 2AFA A‘ with O(s6) states which accepts exactly when A does not. This improves the previously known construction, which was both more complicated (it involved building an intermediate Turing machine) and more expensive (it implied a size blow-up of O(s7)).
