Optimización de autómatas finitos

Abstract

El problema que motiva este trabajo es el de estructurar la información contenida en una base de conocimientos mediante un grafo de herencias así como el desarrollo de algoritmos que resuelvan, con una complejidad razonable, los problemas de construcción y optimización del sistema de representación que se defina. El modelo que se propone en esta tesis se enmarca en los que aprovechan la estructura jerárquica del conocimiento para representarlo como un grafo de conceptos. Esta jerarquía induce una ordenación entre las propiedades de los conceptos, la cual permite utilizar los autómatas finitos no determinísticos (AFNDS) como sistema formal de especificación del modelo, más concretamente la subfamilia de AFNDS que proceden de relaciones de orden. Así el problema de la construcción efectiva y una primera aproximación del algoritmo de optimización se estudian en un contexto formal de autómatas. Para ello se desarrollan en una primera parte de la memoria las herramientas necesarias para el diseño de un algoritmo de orden n4 para la minimización scoop de estos autómatas, el cual se adapta en una segunda parte al caso en que los autómatas se utilizan para representar el conocimiento.