Mathematical Analysis of Lexical-Functional Grammars -Complexity, Parsability, and Learnability-

Cited 0 time in Web of Science Cited 0 time in Scopus

Nishino, Tetsuro

Issue Date
서울대학교 언어교육원
어학연구, Vol.27 No.1, pp. 119-141
In order to specify the syntax of human languages, J. Bresnan and R.M. Kaplan introduced Lexical-Functional Grammars (LFGs) extending context-free grammars (CFGs) by attaching functional equations to each production of CFGs. The LFG theory has been advanced with the aim of meeting the dual demands of parsability and learnability. R. C. Berwick has shown, however, that the membership problem for LFGs is NP-hard and that the LFG theory must be tightened if one wants to avoid computational intractability. In this paper, we first show another formal properties of LFG theory suggesting its computational intractability, which are stated as follows: (1) the emptiness problem for LFGs is undecidable, and (2) the membership problem for LFGs which have one c-production is EXPTIME-hard. Based on this observation, we introduce Frontier-to-Root LFGs (FRLFGs) by restricting the form of functional equations attached to phrase structure rules. Then we show that the membership and parsing problems for FRLFGs can be solved. in O(n²) time if the underlying CFG is unambiguous. Since the famous non context-free language {aᵏbᵏcᵏ|k≥1} can be generated by an unambiguous FRLFG, we obtain that the membership and parsing problems for this language can be solved in O (n²) time. We also show that, given a string χ of the length n, the membership and parsing problems for an FRLFG G can be solved in 0 (n³+d(χ, G) · n) time, where d(χ, G) is the degree of ambiguity of χ with respect to G. Furthermore, we show that there is a polynomial time algorithm to learn the set of annotated phrase structure rules of an unknown FRLFG using structural membership, structural equivalence, and structural output queries. Thus, we propose a sufficiently large subclass of LFGs meeting the dual demands of parsability and learnability from computational theoretic points of view.
Files in This Item:
Appears in Collections:
Language Education Institute (언어교육원)Language Research (어학연구)Language Research (어학연구) Volume 27 Number 1/4 (1991)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.