Resumen de Sobre algunos rasgos característicos de las gramáticas lineales y su aplicación al estudio de su identificación y complejidad
La tesis que aquí se presenta trata acerca del aprendizaje de una clase de lenguajes utilizando un criterio de éxito ya formulado y la resolución de los problemas relacionados con el mismo, entre los que ocupa un papel principal la complejidad descriptiva de las hipótesis formuladas. En este trabajo nos centraremos en las clases de lenguajes lineales. La clase de los lenguajes lineales es de especial interés ya que plantea los problemas característicos que limitan o impiden cierto tipo de aprendizaje: determinismo vs. No determinismo, ambigüedad, equivalencia, etc. Así, nos encontramos en un escenario que nos permite obtener conclusiones válidas para otras clases de lenguajes cuyo interés es, hoy en día, notable. A lo largo de la presente memoria, trabajaremos bajo el criterio de éxito de Identificación en el límite. El criterio seleccionado, dentro de la variedad de criterios posibles (identificacín estocástica, identificación PAC, minimización de entropía, etc). Ha sido ampliamente aceptado por la comunidad científica desde su formulación a mediados de los años sesenta. Este marco de trabajo no impone restricciones acerca de la presentación de ejmplos para los algoritmos de aprendizaje ni tampoco exige un aprendizaje limitado en el tiempo.
Otro aspecto que se estudia en este trabajo es el de la complejidad descriptiva de la clase de los lenguajes lineales. Nos gustaría destacar el hecho de que la identificación de clases de lenguajes y el análisis de la complejidad de las citadas clases, tanto descriptiva como computacional, no son áreas que, como pudiera parecer, no tengan relación. Sucede más bien todo lo contrario. Cuando se reflexiona acerca de cuáles son las representaciones idóneas para representar clases de lenguajes identificables surge, de forma natural, el análisis descriptivo de dichas clases.
