A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars

Sachiko ANDO  Ryuichi NAKANISHI  Hiroyuki SEKI  Tadao KASAMI  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.10   pp.1067-1076
Publication Date: 1994/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata, Languages and Theory of Computing
lexical-functional grammar,  modified head grammar,  formal language,  generative capacity,  

Full Text: PDF>>
Buy this Article

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 -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 vi of v, the f-structure of vi 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(n6) time, the languages generated by pd-lfg's can be recognized in O(n6) time.