Abstract
Following some previous studies on restarting list automata (RLA), we concentrate on a generalized and refined model - the h-lexicalized restarting list automaton (hLxRLA), which is useful for expressing properties of lexicalized syntax in computational linguistics. We present several subclasses of hLxRLA and provide some variants and extensions of the Chomsky hierarchy - the h-lexicalized variants of the Chomsky hierarchy.
We compare the input languages of RLA, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages of hLxRLA, which are used to define h-lexicalized syntactic analysis. The h-lexicalized syntactic analysis allows us to stress several nice syntactic properties of h-lexicalized restarting automata (hRLWW).
We present a transformation from monotone RLWWautomata that recognize the context-free languages (CFL) as their input languages to deterministic monotone hRLWW-automata that compute h-lexicalized syntactic analysis for the whole class CFL through their basic and h-proper languages. Through this transformation, we obtain several types of deterministic hRLWW-automata and hLxRLA-automata that cover h-lexicalized syntactic analyses of CFL and that satisfy the Complete Strong Correctness Preserving Property.