Proceedings

Formal Properties and Implementation of Bidirectional Charts

Download BibTeX Cite

Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Speech and Natural Language. Pages 1480-1484.

© 1989 International Joint Conferences on Artificial Intelligence

Abstract

Several theories of grammar currently converge toward inserting subcategorization information within lexical entries. Such a tendency would benefit from a parsing algorithm able to work from "triggering positions" outward. In this paper a bidirectional extension of the chart algorithm is proposed and its most relevant formal properties are investigated using an Earley like formalism. The question as to whether the proposed approach guarantees computational feasibility is then addressed and is answered affirmatively. Also, it is shown that the method presented here maintains those characteristics that were so much appreciated in monodirectional charts. Finally, from this analysis indications are derived for an efficient implementation of the parsing algorithm.

  1. [Bossi et al., 1983] A. Bossi, N. Cocco and L. Colussi. A divide-and-conquer approach to general context-free parsing. Information Processing Letters, 16 -pp. 203- 208, 1983.
  2. [Earley, 1970] Jay Earley. An Efficient Context-Free Parsing Algorithm. Communications of the ACM, 13 - pp. 94-102, 1970.
  3. [Graham and Harrison, 1976] Susan L. Graham and Michael A. Harrison. Parsing of General Context Free Languages. Advances in Computers-pp. 77-185 -, Academic Press, New York, 1976.
  4. [Jackendoff, 1977] Ray Jackendoff. X-bar Syntax: A Study of Phrase Structure. The MIT Press, Cambridge, Massachusetts, 1977.
  5. [Kaplan, 1973] Ronald M. Kaplan. 1973. A General Syntactic Processor. In: (R. Rustin, ed) Natural Language Processing -pp. 193-241 -, Algorithmics Press, New York, New York, 1973.
  6. Kaplan and Bresnan 1982]
  7. Ronald M. Kaplan and Joan Bresnan. Lexical Functional Grammar: A Formal System for Grammatical Representation. In: (J. Bresnan, ed) The Mental Representation of Grammatical Relations-pp. 173-281-, The MIT Press, 1982.
  8. [Kay, 1973] Martin Kay. The MIND System. In: (R. Rustin, ed) Natural Language Processing-pp. 155-188- , Algorithmics Press, New York, New York, 1973.
  9. [Kay, 1980] Martin Kay. Algorithm Schemata and Data Structures in Syntactic Processing. Tecnical Report CSL-80 Xerox-PARC, Palo Alto, California, 1980.
  10. [Sag and Pollard, 1987] Ivan Sag and Carl Pollard. Head Driven Phrase Structure Grammar: An Informal Synopsis.. Report No. CSLI 87-79, CSLI, Stanford University, Stanford, 1987.
  11. [Satta, 1988] Giorgio Satta. Some Results for a Bidirectional Extension of Earley's Algorithm. Draft, IRST, Trento, 1988.
  12. [Steel and De Roeck, 1987] Sam Steel and Anne De Roeck. Bidirectional Chart Parsing. Proceedings of A/SB-87, Edinburgh, Scotland, 1987.
  13. [Stock et al., 1989] Oliviero Stock, Rino Falcone and Patrizia Insinnamo. Bidirectional Charts: a Potential Technique for Parsing Spoken Natural Language. Computer Speech and Language, 3, 1989.
  14. [Thompson and Ritchie, 1984] Henry Thompson and Graeme Ritchie. Implementing Natural Language Parsers. In: (T. O'Shea, M. Eisenstadt eds) Artificial Intelligence-pp. 245-300 -,Harper & Row, New York, 1985.
  15. [Wang, 1985] Weigno Wang. Computational Linguistics Technical Notes No. 2.. Technical Report 85/013, Computer Science Department, Boston University, Boston, Massachusetts, 1985.
  16. [Wiren, 1987] Mats Wiren. A Comparison of Rule- Invocation Strategies in Context-Free Parsing. Proceedings of the 3rd Conference of the European Chapter of the Association for Computational Linguistics, Copenhagen, Denmark, 1987.

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

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