Unary Versus Binary Two-Way Automata

Viliam Geffert, Vincent Hlaváč, Rastislav Královič

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 in L. It is known that if a unary language L…