
For FullText 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 PolynomialTime Recognizable Subclass of LexicalFunctional Grammars
Sachiko ANDO Ryuichi NAKANISHI Hiroyuki SEKI Tadao KASAMI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E77D
No.10
pp.10671076 Publication Date: 1994/10/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Automata, Languages and Theory of Computing Keyword: lexicalfunctional grammar, modified head grammar, formal language, generative capacity,
Full Text: PDF>>
Summary:
Lexicalfunctional grammars (lfg's) were introduced to define the syntax of natural languages. In lfg's, a finite set of attributevalue pairs called an fstructure 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 pdlfg's. In pdlfg's, an fstructure forms a pushdown stack. For a node v in a derivation tree and at most one specified child v_{i} of v, the fstructure of v_{i} is obtained by performing a specified pushdown stack operation on the fstructure of v. We prove the equivalence of the generative capacity of modified head grammars (mhg's) and that of pdlfg's. Since the languages generated by mhg's are known to be recognizable in O(n^{6}) time, the languages generated by pdlfg's can be recognized in O(n^{6}) time.

