Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Earley's Algorithm

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.



Add Comment

No comments.