Unary Versus Binary Two-Way Automata
Viliam Geffert, Vincent Hlaváč, Rastislav Kráľovič · Electronic Proceedings in Theoretical Computer Science · 2026
If L is a unary language, then its binary coded version bin L is a binary language containing all binary strings representing any 0 x ∈ L. It it known that if a unary language L is regular and can be recognized by a minimal one-way deterministic finite automaton (1DFA) with n states, then its binary coded version is also regular and can be recognized by a 1DFA with at most n states, but at least 1+ log n states.Here we shall present related results for two-way automata (2DFAs).First, we shall show that each unary 2DFA A 1 with n states can be converted to a 2DFA A 2 recognizing bin L(A 1 ) with at most O(n•log n) states.If A 1 is minimal and uses only loops of odd lengths, A 2 will use at most 2n+2 states, but it must use at least n states.For each n ≥ 7, we shall also present a unary witness language for which a minimal 2DFA uses exactly n states, but any minimal 2DFA recognizing its binary coded version uses at least n states, but less than n+ log n states.