Limited Automata and Context-Free Languages
Giovanni Pighizzini, Andrea Pisoni · Fundamenta Informaticae · 2015
Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalen