A Probabilistic Chart Parser implemented with an Evolutionary Algorithm.
Lourdes Araujo.
International Conference on Intelligent Text Processing and Computational Linguistics CICLing-2004.
Lecture Notes in Computer Science2945, p. 81-92, Springer-Verlag.

Classic parsing methods use complete search techniques to find the
different interpretations of a sentence. However, the size of the search
space increases exponentially with the length of the sentence or text to
be parsed and the size of the grammar, so that exhaustive search methods
can fail to reach a solution in a reasonable time. Nevertheless, large
problems can be solved approximately by some kind of stochastic techniques,
which do not guarantee the optimum value, but allow adjusting the
probability of error by increasing the number of points explored.
Evolutionary Algorithms are among such techniques. This paper presents a
stochastic chart parser based on an evolutionary algorithm which works
with a population of partial parsings. The paper describes the relationships
between the elements of a classic chart parser and those of the evolutionary
algorithm. The model has been implemented, and the results obtained for texts
extracted from the Susanne corpus are presented.