1-Limited Automata: Witness Languages and Techniques

1-limited automata are single-tape Turing machines with strong rewriting restrictions, that do not allow them to recognize more than regular languages. However, 1-limited automata can be significantly more succinct than equivalent finite automata: in fact, the size gap from 1-limited automata to one-way deterministic finite automata is double exponential. In this paper we present and discuss some languages which can be used as witnesses of the gaps between different kinds of 1-limited automata and finite automata. Among them, refining previous techniques, we show that a language proposed long time ago by Meyer and Fischer as a witness of the optimality of the subset construction for finite state automata, can also be used as witness of all the currently known size gaps between 1-limited automata and different variants of finite automata. We also discuss some open problems and possible further lines of investigation.