Proceedings

Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Natural-language Processing and Graphical Presentation. Pages 1002-1008.

© 1997 International Joint Conferences on Artificial Intelligence

Abstract

Recently researchers working in the LFG framework have proposed algorithms for taking advantage of the implicit context-free components of a unification grammar [Maxwell and Kaplan, 19961 This paper clarifies the mathematical foundations of these techniques, provides a uniform framework in which they can be formally studied and eliminates the need for special purpose runtime datastructures recording ambiguity. The paper posits the identity: Ambiguous Feature Structures = Grammars, which states that (finitely) ambiguous representations are best seen as unification grammars of a certain type, here called "interactionfree" grammars, which generate in a backtrackfree way each of the feature structures subsumed by the ambiguous representation. This work extends a line of research [Billot and Lang, 1989; Lang, 1994] which stresses the connection between charts and grammars: a chart can be seen as a specialization of the reference grammar for a given input string. We show how this specialization grammar can be transformed into an interaction-free form which has the same practicality as a listing of the individual solutions, but is produced in less time and space.

  1. [Bar-Hillel et al., 1961] Y. Bar-Hillel. M. Perles, and E Shamir. On formal properties of simple phrase structure grammars. Zeitschrift fur Phonetik, Sprachwissenschaft und Kommunicationsforschung,14:142-172,1961.
  2. [Billot and Lang, 1989] S. Billot and B. Lang. The structure of shared forests in ambiguous parsing. In 27th Meeting of the Association for Computational Linguistics, 1989.
  3. [Colmerauer, 1984] A. Colmerauer. Equations and Inequa- tions on Finite and Infinite Trees. In Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS-84), pages 85-99, Tokyo, Japan, Novem- ber 1984. ICOT.
  4. [Joshi, 1985] A. K. Joshi. How much context-sensitivity is required to provide reasonable structural descriptions: Tree adjoining grammars. In D. Dowty. L. Karttunen, and A. Zwicky. editors. Natural Language Parsing : Psy- cholinguistic, Computational and Theoretical Perspec- tives, pages 206-250. Cambridge University Press. New York.1985.
  5. Joshi. 1987]
  6. Aravind K. Joshi. The convergence of mildly context-sensitive grammatical formalisms. Presented at the Workshop on Processing of Linguistic Structure, Santa Cruz. 1987.
  7. [Kaplan and Bresnan, 1982] R. Kaplan and J. Bresnan. Lex- ical functional grammar: A formal system for grammatical representation. In J. Bresnan. editor. The mental represen- tation of grammatical relations. MIT press, Cambridge.
  8. MA,1982.
  9. fLang. 1994]
  10. Bernard Lang. Recognition can be harder than parsing. Computational Intelligence, 10, 1994.
  11. [Maxwell and Kaplan, 1990] J. T Maxwell and R. Kaplan. A Method for Disjunctive Constraint Satisfaction. Technical Report SSL-90-06, Xerox Pare. (Palo Alto Research Cen- ter). June 1990.
  12. [Maxwell and Kaplan, 1993] John T. Maxwell and Ronald M. Kaplan. The interface be- tween phrasal and functional constraints. Computational Linguistics, 19( 4):571-590, December 1993.
  13. [Maxwell and Kaplan, 1996] John T. Maxwell and Ronald M. Kaplan. An ef- ficient parser for lfg. In First LFG Conference, Grenoble, France, August 1996. http: I / www- c sli . stanford.edu/user/mutt/. Link
  14. [rPereira and Shieber, 1987] Fernando C. N. Pereira and Stu- art M. Shieber. Prolog and Natural-Language Analysis, volume 10 of CSU Lecture Notes. Chicago University Press. Stanford, 1987.
  15. rPereira and Warren,l980]
  16. Fernando C. N. Pereira and David H. D. Warren. Definite clause grammars for lan- guage analysis. Artificial Intelligence, 13:231-278,1980.
  17. [rPereira and Warren, 1983] Fernando C. N. Pereira and David H. D. Warren. Parsing as deduction. In Proceedings of the 21th Annual Meeting of the Association for Com- putational Linguistics, pages 137-144, MIT. Cambridge, MA. June 1983.
  18. [Vijay-Shanker and Weir, 1994] K. Vijay-Shanker and D. J. Weir. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27(6):511-546, November/December 1994.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards