The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Sachiko ANDO(1hit)

1-1hit
  • A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars

    Sachiko ANDO  Ryuichi NAKANISHI  Hiroyuki SEKI  Tadao KASAMI  

     
    PAPER-Automata, Languages and Theory of Computing

      Vol:
    E77-D No:10
      Page(s):
    1067-1076

    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.