Counting with range concatenation grammars

摘要

The class of range concatenation grammars appears to be a convincing challenger as a syntactic base for various tasks, especially in natural language processing. These grammars are powerful, since they strictly contain the class of mildly context-sensitive formalisms, while staying computationally tractable, since their sentences can be parsed in polynomial time. The output of their parsers are structures of polynomial size that can be seen as a generalization of classical context-free shared forest. Moreover, this formalism allows a form of modularity which may lead to the design of libraries of reusable grammatical components. And, finally, it can act as a syntactic backbone upon which decorations from other domains (say feature structures) can be grafted. In this paper we explore the behavior of range concatenation grammars in counting, a domain in which bad reputation of other classical syntactic formalisms is well known. This study leads to some surprising results.