Abstract
We study h-lexicalized two-way restarting automaton (hRLWW(i)) that can rewrite at most i times per cycle, for i GREATER-THAN OR EQUAL TO 1. This model is useful for the study of lexical syntactic disambiguation (a notion from linguistic) through the formal notion of h-lexicalized syntactic analysis (hLSA).
The hLSA is composed of a basic language and the corresponding h-proper language obtained from the basic language by mapping all non-input symbols on input symbols. We compare the properties of input languages, which are the languages traditionally considered in automata theory, to the properties of hLSA, i.e., to the properties of basic and h-proper languages.
The basic and h-proper languages of hRLWW(i)- automata fulfill the so called reduction correctness preserving property, but the input languages do not. While basic and h-proper languages are sensitive to the size of the read/write window, the input languages are not.
Moreover, the basic and h-proper languages are sensitive to the number of rewrite steps per cycle. All that concerns a subclass of context-sensitive languages containing all contextfree languages (and most probably also the class of mildly context-sensitive languages [5]), i.e., a class suitable for studying and classifying syntactic and semantic features of natural languages.
We work here also with the parametrized constraint of monotonicity. While using the monotonicity of degree one we can characterize the class of context-free languages, the monotonicity of higher degrees can model more complex syntactic phenomena of whole natural languages (like cross-serial dependencies [5]).
Finally, we stress the constraint of weak cyclic form. It preserves the power of hRLWW(i)-automata, and it allows to extend the complexity results obtained for the classes of infinite languages also into the classes of finite languages (parametrized by the number of performed cycles).
It is useful for classifications in computational and corpus linguistics, where all the (syntactic) observation are of the finite nature. The main technical novelty of the paper are the results about the sensitivity and insensivity of finite and infinite hLSA and corresponding languages by hRLWW(i)- automata.