Linear List Automata with a Look-Ahead Window

Abstract

Linear list automata constitute an interesting class of acceptors which has a remarkable `explicatory power' w.r.t. the analysis of formal and natural languages. We consider a more general model where each automaton has a (fixed-size) look-ahead window attached to its head.

We present a refinement of the Chomsky hierarchy, and display the classes of automata which can support bottom-up analysis. The work is meant as a preparation for a further generalization, which will combine linear list automata and restarting automata.