Revisando el reconocedor con prefijo válido para TAGs de Schabes

Abstract

Garantizar la propiedad del prefijo válido en el reconocimiento de lenguajes para Gramáticas de Adjunción de Árboles (TAG, Tree Adjoining Grammars) supone una dificultad añadida en la definición de reconocedores. El reconocedor propuesto por Nederhof es actualmente la mejor solución, O(n6), siendo n el tamaño de la cadena de entrada. Existe una propuesta anterior debida a Schabes con coste O(n9). Este trabajo presenta un estudio de este último reconocedor, que lo adaptará dentro del paradigma de analizadores deductivos utilizando la misma notación del reconocedor de Nederhof. Después se presentará una reducción de su complejidad de O(n9) a O(n7) y, finalmente, se concluirá que los reconocedores de Nederhof y de Schabes están íntimamente relacionados.