Catalogue of Artificial Intelligence Techniques
Keywords: parsing, recognition, well-formed substring table
Categories: Natural Language
Author(s): Henry Thompson
The first published algorithm to bring the worst-case asymptotic time complexity of recognition for unrestricted Context-free Grammars down to cubic order in the number of words in the string to be parsed. Makes use of a well-formed substring table. See Caching.
- Earley, J., An efficient context-free parsing algorithm Communications of the ACM 13 (1970) no.2, 94--102, also appears in Readings in Natural Language Processing
(Grosz, B.J., Sp.