Lexicalized Syntactic Analysis by Two-Way Restarting Automata
František Mráz, Friedrich Otto, Dana Pardubská, Martin Plátek · Journal of automata, languages and combinatorics · 2021
We study \emph{h-lexicalized two-way restarting automat{a}} that can rewrite at most $i$ times per cycle for some $i\ge 1$ (\hRLWW$(i)$-automata). This model is useful for the study of lexical (syntactic) disambiguation, which is a concept from linguistics that is based on certain reduction patterns. We study lexical disambiguation through the formal notion of \emph{h-lexicalized syntactic analysis} (hLSA). The hLSA is a relation between a \emph{basic language} and the corresponding \emph{h-proper language}, which is obtained from the basic language by mapping all basic symbols {to} input symbols. We stress the sensitivity of hLSA by~\hRLWW$(i)$-automata to the size of the window, the number of possible rewrites per cycle, and the degree of (non-)monotonicity of these automata. We introduce the concepts of \emph{contextually transparent languages} and \emph{contextually transparent lexicalized analyses} based on very special reduction patterns, and we present two-dimensional hierarchies of their subclasses based on the size of the window and on the degree of monotonicity. The bottoms of these hierarchies correspond to the regular and the context-free languages. The class of contextually transparent languages forms a proper subclass of the class of context-sensitive languages with syntactically natural properties.