tailieunhanh - Báo cáo khoa học: "Chinese Numbers, MIX, Scrambling, and Range Concatenation Grammars"

The notion of mild context-sensitivity was formulated in an attempt to express the formal power which is both necessary and sufficient to define the syntax of natural languages. However, some linguistic phenomena such as Chinese numbers and German word scrambling lie beyond the realm of mildly contextsensitive formalisms. On the other hand, the class of range concatenation grammars provides added power , mildly context-sensitive grammars while keeping a polynomial parse time behavior. In this report, we show that this increased power can be used to define the abovementioned linguistic phenomena with a polynomial parse time of a very low. | Proceedings of EACL 99 Chinese Numbers MIX Scrambling and Range Concatenation Grammars Pierre Boullier INRIA-Rocquencourt Domaine de Voluceau . 105 78153 Le Chesnay Cedex France Abstract The notion of mild context-sensitivity was formulated in an attempt to express the formal power which is both necessary and sufficient to define the syntax of natural languages. However some linguistic phenomena such as Chinese numbers and German word scrambling lie beyond the realm of mildly context-sensitive formalisms. On the other hand the class of range concatenation grammars provides added power . mildly context-sensitive grammars while keeping a polynomial parse time behavior. In this report we show that this increased power can be used to define the above-mentioned linguistic phenomena with a polynomial parse time of a very low degree. 1 Motivation The notion of mild context-sensitivity originates in an attempt by Joshi 85 to express the formal power needed to define the syntax of natural languages NLs . We know that context-free grammars CFGs are not adequate to define NLs since some phenomena are beyond their power see Shieber 85 . Popular incarnations of mildly context-sensitive MCS formalisms are tree adjoining grammars TAGs Vijay-Shanker 87 and linear context-free rewriting LCFR systems Vijay-Shanker Weir and Joshi 87 . However there are some linguistic phenomena which are known to lie beyond MCS formalisms. Chinese numbers have been studied in Radzinski 91 where it is shown that the set of these numbers is not a LCFR language and that it appears also not to be MCS since it violates the constant growth property. Scrambling is a word-order phenomenon which also lies beyond LCFR systems see Becker Rambow and Niv 92 . On the other hand range concatenation grammar RCG presented in Boullier 98a is a syntactic formalism which is a variant of simple literal movement grammar LMG described in Groenink 97 and which is also related to the .