For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
Sachiko ANDO Ryuichi NAKANISHI Hiroyuki SEKI Tadao KASAMI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/10/25
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>>
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.