tailieunhanh - Báo cáo khoa học: "PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS, FINITE-STATE TRANSLATION SYSTEMS, AND POLYNOMIAL-TIME RECOGNIZABLE SUBCLASSES OF LEXICAL-FUNCTIONAL GRAMMARS"

A number of grammatical formalisms were introduced to define the syntax of natural languages. Among them are parallel multiple context-free grammars (pmcfg's) and lexical-functional grammars (lfg's). Pmcfg's and their subclass called multiple context-free grammars (mcfg's) are natural extensions of cfg's, and pmcfg's are known to be recognizable in polynomial time. Some subclasses of lfg's have been proposed, but they were shown to generate an AlP-complete language. Finite state translation systems (fts') were introduced as a computational model of transformational grammars. . | PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS FINITE-STATE TRANSLATION SYSTEMS AND POLYNOMIAL-TIME RECOGNIZABLE SUBCLASSES OF LEXICAL-FUNCTIONAL GRAMMARS Hiroyuki Seki B Ryuichi Nakanishi t Yuichi Kaji t Sachiko Ando t Tadao Kasami p 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@ Abstract A number of grammatical formalisms were introduced to define the syntax of natural languages. Among them are parallel multiple context-free grammars pmcfg s and lexical-functional grammars Ifg s . Pmcfg s and their subclass called multiple context-free grammars mcfg s are natural extensions of cfg s and pmcfg s are known to be recognizable in polynomial time. Some subclasses of Ifg s have been proposed but they were shown to generate an A P-complete language. Finite state translation systems fts were introduced as a computational model of transformational grammars. In this paper three subclasses of Ifg 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 investigated. 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 deterministic 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 A P-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 A P. 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