A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars

概要

論文の詳細を見る
Lexical-functional grammars (lfg's) were introduced to define the syntax of natural languages. In lfg's, a finite set of attribute-value pairs called an f-structure is associated with each internal node in a derivation tree. For efficient parsing, some subclasses of lfg's were proposed. However, these subclasses have been shown to generate at least one NP-complete language. In this paper, we introduce a subclass of lfg's called pd-lfg's. In pd-lfg's, an f-structure forms a pushdown stack. For a node v in a derivation tree and at most one specified child v_i of v, the f-structure of v_i is obtained by performing a specified pushdown stack operation on the f-structure of v. We prove the equivalence of the generative capacity of modified head grammars (mhg's) and that of pd-lfg's. Since the languages generated by mhg's are known to be recognizable in O(n^6) time, the languages generated by pd-lfg's can be recognized in O(n^6) time.
社団法人電子情報通信学会の論文
1994-10-25