tailieunhanh - Báo cáo khoa học: "On the Applicability of Global Index Grammars"

We investigate Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We discuss some of the structural descriptions that GIGs can generate compared with those generated by LIGs. We show also how GIGs can represent structural descriptions corresponding to HPSGs (Pollard and Sag, 1994) schemas. | On the Applicability of Global Index Grammars Jose M. Castano Computer Science Department Brandeis University jcastano@ Abstract We investigate Global Index Grammars GIGs a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We discuss some of the structural descriptions that GIGs can generate compared with those generated by LIGs. We show also how GIGs can represent structural descriptions corresponding to HPSGs Pollard and Sag 1994 schemas. 1 Introduction The notion of Mildly context-sensitivity was introduced in Joshi 1985 as a possible model to express the required properties of formalisms that might describe Natural Language NL phenomena. It requires three properties 1 a constant growth property or the stronger semilinearity property b polynomial parsability c limited cross-serial dependencies . some limited context-sensitivity. The canonical NL problems which exceed context free power are multiple agreements reduplication crossing Mildly Context-sensitive Languages MCSLs have been characterized by a geometric hierarchy of grammar levels. A level-2 MCSL eg. 1See for example Joshi et al. 1991 Weir 1988 . 2However other phenomena . scrambling Georgian Case and Chinese numbers might be considered to be beyond certain mildly context-sensitive formalisms. TALs LILs is able to capture up to 4 counting dependencies includes L i fanbncndn n 1 but not L5 fanbncndnen n 1 . They were proven to have recognition algorithms with time complexity O n6 Satta 1994 . In general for a level-fc MCSL the recognition problem is in O n5 2 1 and the descriptive power regarding counting dependencies is 2k Weir 1988 . Even the descriptive power of level-2 MCSLs Tree Adjoining Grammars TAGs Linear Indexed Grammars LIGs Combinatory Categorial Grammars CCGs might be considered insufficient for some NL problems therefore there have been many proposals3 to extend or modify them. On our view