On h-Lexicalized Restarting Automata Article Swipe
YOU?
·
· 2017
· Open Access
·
· DOI: https://doi.org/10.4204/eptcs.252.21
· OA: W2747328602
Following some previous studies on restarting automata, we introduce a\nrefined model - the h-lexicalized restarting automaton (h-RLWW). We argue that\nthis model is useful for expressing lexicalized syntax in computational\nlinguistics. We compare the input languages, which are the languages\ntraditionally considered in automata theory, to the so-called basic and\nh-proper languages, which are (implicitly) used by categorial grammars, the\noriginal tool for the description of lexicalized syntax. The basic and h-proper\nlanguages allow us to stress several nice properties of h-lexicalized\nrestarting automata, and they are suitable for modeling the analysis by\nreduction and, subsequently, for the development of categories of a lexicalized\nsyntax. Based on the fact that a two-way deterministic monotone restarting\nautomaton can be transformed into an equivalent deterministic monotone\nRL-automaton in (Marcus) contextual form, we obtain a transformation from\nmonotone RLWW-automata that recognize the class CFL of context-free languages\nas their input languages to deterministic monotone h-RLWW-automata that\nrecognize CFL through their h-proper languages. Through this transformation we\nobtain automata with the complete correctness preserving property and an\ninfinite hierarchy within CFL, based on the size of the read/write window.\nAdditionally, we consider h-RLWW-automata that are allowed to perform multiple\nrewrite steps per cycle, and we establish another infinite hierarchy above CFL\nthat is based on the number of rewrite steps that may be executed within a\ncycle. The corresponding separation results and their proofs illustrate the\ntransparency of h-RLWW-automata that work with the (complete or cyclic)\ncorrectness preserving property\n
