Parallel Multiple Context-Free Grammars, Finite-State Translation Systems, and Polynomial-Time Recognizable Subclasses of Lexical-Functional Grammars

PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS, FINITE-STATE TRANSLATION SYSTEMS, AND POLYNOMIAL-TIME RECOGNIZABLE SUBCLASSES OF LEXICAL-FUNCTIONAL GRAMMARS Hiroyuki Seki tt Ryuichi Nakanishi t Yuichi Kaji t Sachiko Ando t Tadao Kasami $t t Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University 1-1 Machikaneyama, Toyonaka, Osaka 560, Japan :~ Graduate School of Information Science, Advanced Institute of Science and Technology, Nara 8916-5 Takayama, Ikoma, Nara 630-01, Japan Internet: seki@ics.es.osaka-u.ac.jp Abstract 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 show that the generative capacity of fts' is equal to that of nc-lfg's. As relations among subclasses of those formalisms, it is shown that the generative capacities of de- terministic fts', dc-lfg's, and pmcfg's are equal to each other, and the generative capacity of fc-lfg's is equal to that of mcfg's. It is also shown that at least one Af79-complete language is generated by fts'. Consequently, deterministic fts', dc-lfg's and fc-lfg's can be recognized in polynomial time. However, fts' (and nc-lfg's) cannot, if P ¢ AfT 9. 1 Introduction A number of grammatical formalisms such as lexical-functional grammars (Kaplan 1982), head grammars (Pollard 1984) and tree adjoining grammars (Joshi 1975)(Vijay-Shanker 1987) were introduced to define the syntax of natural lan- guages. On the other hand, there has been much effort to propose well-defined computa- tional models of transformational grammars. One of these is the one to extend devices which oper- ate on strings, such as generalized sequential ma- chines (gsm's) to devices which operate on trees. It is fundamentally significant to clarify the gen- erative capacities of such grammars and devices. Parallel multiple context-free grammars (pm- cfg's) and multiple context-free grammars (mcfg's) were introduced in (Kasami 1988a)(Seki 1991) as natural extensions of cfg's. The subsystem of lin- ear context-free rewriting systems (Icfrs') (Vijay- Shanker 1987) which deals with only strings is the same formalism as mcfg's. The class of cfl's is properly included in the class of languages gen- erated by pmcfg's, which in turn is properly in- cluded in the one generated by mcfg's. The class of languages generated by pmcfg's is properly included in that of context-sensitive languages (Kasami 1988a). Pmcfg's have been shown to be recognized in polynomial time (Kasami 1988b)(Seki 1991). A tree transducer (Rounds 1969) takes a tree as an input, starts from the initial state with its head scanning the root node of an input. Ac- cording to …

Content truncated to 500 words