Programación dinámica y análisis parcial

En los últimos años hemos observado un renovado interés en la aplicación de la programación dinámica al procesamiento del lenguaje natural (PLN). La principal ventaja es la compactación de las representaciones, lo que convierte este paradigma en un método común para el tratamiento de computaciones con un alto grado de redundancia relacionado con fenómenos como el no determinismo. El análisis sintáctico del lenguaje natural añade otro desafío, ya que a menudo la información gramatical no es suficiente. En el presente trabajo describimos una extensión de las técnicas de análisis para el caso del análisis parcial en programación dinámica. Nuestro objetivo es obtener tanta información como sea posible, esto es, análisis incompletos, al mismo tiempo que conservamos la compactación de las representaciones.The last years have seen a renewal of interest in applying dynamic programming to natural language processing. The main advantage is the compactness of the representations, which is turning this paradigm into a common way of dealing with highly redundant computations related to phenomena such as non-determinism. Natural language parsing adds another challenge, since grammatical information is often insufficient. We describe an extension of parsing techniques for partial parsing in dynamic programming. Our aim is to obtain as much information as possible, that is incomplete parses, while preserving compactness of the representations.Este trabajo ha sido parcialmente financiado por la Unión Europea, el Gobierno español y la Xunta de Galicia mediante los proyectos 1FD97-0047-C04-02, TIC2000-0370-C02-01 y PGIDT99XI10502B, respectivamente