Iterated Dependencies and Kleene Iteration

摘要

Categorial Dependency Grammars (CDG) is a class of simple and expressive categorial grammars defining projective and discontinuous dependency structures in a strongly compositional way. They are more expressive than CF-grammars, are polynomial time recognizable and different from the mildly context sensitive grammars. CDG languages are proved to be closed under all AFL operations, but iteration. In this paper, we explain the connection between the iteration closure and the iterated dependencies (optional repeatable dependencies, inevitable in dependency syntax) and show that the CDG extended by a natural multimodal rule define an AFL, but the membership problem in this extended family is NP-complete.