Optimización de autómatas finitos

Abstract

EL PROBLEMA QUE MOTIVA ESTE TRABAJO ES EL DE ESTRUCTURAR LA INFORMACION CONTENIDA EN UNA BASE DE CONOCIMIENTOS MEDIANTE UN GRAFO DE HERENCIAS ASI COMO EL DESARROLLO DE ALGORITMOS QUE RESUELVAN, CON UNA COMPLEJIDAD RAZONABLE, LOS PROBLEMAS DE CONSTRUCCION Y OPTIMIZACION DEL SISTEMA DE REPRESENTACION QUE SE DEFINA, EL MODELO QUE SE PROPONE EN ESTA TESIS SE ENMARCA EN LOS QUE APROVECHAN LA ESTRUCTURA JERARQUICA DEL CONOCIMIENTO PARA REPRESENTARLO COMO UN GRAFO DE CONCEPTOS. ESTA JERARQUIA INDUCE UNA ORDENACION ENTRE LAS PROPIEDADES DE LOS CONCEPTOS, LA CUAL PERMITE UTILIZAR LOS AUTOMATAS FINITOS NO DETERMINISTICOS (AFNDS) COMO SISTEMA FORMAL DE ESPECIFICACION DEL MODELO, MAS CONCRETAMENTE LA SUBFAMILIA DE AFNDS QUE PROCEDEN DE RELACIONES DE ORDEN. ASI EL PROBLEMA DE LA CONSTRUCCION EFECTIVA Y UNA PRIMERA APROXIMACION DEL ALGORITMO DE OPTIMIZACION SE ESTUDIA EN UN CONTEXTO FORMAL DE AUTOMATAS. 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 MINIMIZACION SCOOP DE ESTOS AUTOMATAS, EL CUAL SE ADAPTA EN UNA SEGUNDA PARTE AL CASO EN QUE LOS AUTOMATAS SE UTILIZAN PARA REPRESENTAR EL CONOCIMIENTO.