Multi-Head Two-Way Finite Automata with Advice
Ahmet Bilal Uçan · International Journal of Foundations of Computer Science · 2025
We reject the proposed proofs of “Lemma 9” and “Theorem 13” of an article by Frei et al. by pointing out fatal errors in them. In addition, we proved a result that contradicts the latter. We show that it is possible to trade input heads with advice heads and vice versa as long as all heads are allowed to move in both directions and the advice length is not too long and short. We proved that the advice gap between determinism and non-determinism is exponential when there are multiple advice heads, all of which can move in both directions and an input head that cannot move left.