Paper: Parallel Multiple Context-Free Grammars Finite-State Translation Systems And Polynomial-Time Recognizable Subclasses Of Lexical-Functional Grammars

ACL ID P93-1018
Title Parallel Multiple Context-Free Grammars Finite-State Translation Systems And Polynomial-Time Recognizable Subclasses Of Lexical-Functional Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1993
Authors

A number of grammatical formalisms were intro- duced to define the syntax of natural languages. Among them are parallel multiple context-free grammars (pmcfg's) and lexical-functional gram- mars (lfg's). Pmcfg's and their subclass called multiple context-free grammars (mcfg's) are nat- ural extensions of cfg's, and pmcfg's are known to be recognizable in polynomial time. Some sub- classes of lfg's have been proposed, but they were shown to generate an AlP-complete language. Fi- nite state translation systems (fts') were intro- duced as a computational model of transforma- tional grammars. In this paper, three subclasses of lfg's called nc-lfg's, dc-lfg's and fc-lfg's are introduced and the generative capacities of the above mentioned grammatical formalisms are in- vestigated. First, we sho...