Examinando por Materia "Autómatas"

Mostrando 1 - 2 de 2
  • Miniatura
    PublicaciónAcceso abierto
    Comparación de dos algoritmos recientes para inferencia gramatical de lenguajes regulares mediante autómatas no deterministas.
    (2011-10-13) Álvarez, Gloria I.; García, Pedro; Ruiz, José
    El desarrollo de nuevos algoritmos, que resulten convergentes y eficientes, es un paso necesario para un uso provechoso de la inferencia gramatical en la solución de problemas reales y de mayor tamaño. En este trabajo se presentan dos algoritmos llamados DeLeTe2 y MRIA, que implementan la inferencia gramatical por medio de autómatas no deterministas, en contraste con los algoritmos más comúnmente empleados, los cuales utilizan autómatas deterministas. Se consideran las ventajas y desventajas de este cambio en el modelo de representación, mediante la descripción detallada y la comparación de los dos algoritmos de inferencia con respecto al enfoque utilizado en su implementación, a su complejidad computacional, a sus criterios de terminación y a su desempeño sobre un cuerpo de datos sintéticos.
  • Miniatura
    PublicaciónAcceso abierto
    Existencia de coálgebras finales para funtores polinomiales
    (Universidad del Valle, 2011) Téllez Crespo, Andrés Felipe; Ortiz Rico, Guillermo
    El trabajo es una reconstrucción de un resultado que dice que todo funtor polinomial Kripke tiene asociada una coálgebra final, este resultado fue probado por primera vez en 1989 por P. Aczel y N. Mendler en la revista Category Theory and Computer Science número 389 en las páginas 357- 365. La reconstrucción se basó en varios textos pero principalmente en el trabajo de Bart Jacobs del libro Introduction to Coalgebra. Towards Mathematics of States and Observations. Se usa éste por su facilidad de asociar los diferentes resultados a ejemplos básicos de las ciencias de la computación. En el desarrollo del trabajo se usa lenguaje de categorías, se hace una introducción sencilla a los conceptos propios de las coálgebras como Bisimulación, Invariantes, funtor adjunto y un poco de lógica temporal junto con algunos ejemplos en ciencias de la computación para visualizar mejor los conceptos, esto prepara el terreno para la prueba del resultado de existencia de coálgebra final. Luego se prueban resultados importantes que son consecuencia de la existencia de una coálgebra final. Estos resultados incluyen: la construcción de coálgebras colibres, la completez de la categoría de las coálgebras que para estos funtores es bicompleta y por último se demuestra el Principio de Prueba Coinductiva