Resumen

En este trabajo se desarrolla un algoritmo de inferencia gramatical, el cual posee como entrada un conjunto finito de árboles y como salida top-down tree generator (td generador), que consiste de una gramática de árbol regular y un conjunto finito de transductores. Se presenta también el sistema de software TreeBag (Tree Based Generador), herramienta útil para la generación y visualización de objetos de todo tipo: grafos, árboles, string, etc.

INTRODUCCIÓN

En muchas áreas de las ciencias de la computación es frecuente representar la información por árboles o grafos, que son objetos muy apropiados para describir conocimientos, información o representar modelos. Ahora cualquier cambio local que pueda afectar a un árbol o grafo puede quedar registrado a través de una regla o producción, de manera que cualquier proceso dinámico que represente cambios de estado puede representarse a través de un conjunto de reglas. Las reglas y árboles que intervienen en este proceso conforman las llamadas gramáticas de árbol, las cuales proporcionan una alternativa para representar la información de una forma más general, en vez de utilizar cadenas de caracteres, facilitando de esta manera el acceso a un amplio espectro de aplicaciones en diversas áreas, como, por ejemplo: Reconocimiento sintáctico de formas, inferencia gramatical, semántica de lenguajes, así como en la generación sistemática y manipulación de diseños gráficos o, en la Bioinformática, a través de la aplicación de la computación a secuencias biológicas, tales como DNA o proteínas. Vea [1, 14, 13, 7 y 21].

En particular, tratamos en este trabajo el problema de la inferencia gramatical, el cual se refiere a encontrar una descripción sintáctica, por ejemplo Gramáticas, Autómatas, Transductores o algún sistema, en nuestro caso un Sistema Generador de Árboles con Intérprete que consta de gramáticas de árbol, un conjunto finito de transductores y un álgebra (en nuestro caso álgebras Collage que actúan como intérprete), permitiendo la generación o el reconocimiento automático de un conjunto finito de modelos en S₊, que es un conjunto finito de modelos pertenecientes a algún lenguaje, también llamados ejemplos positivos, los que en general pueden ser cadenas de caracteres, árboles, grafos, modelos u otros, en nuestro caso son árboles, y posiblemente un conjunto de árboles del complemento de S₊, también llamados ejemplos negativos. Para mayor información, vea [18].

Una gran variedad de algoritmos de inferencia se han desarrollado, por ejemplo, Fu y Booth [6] genera gramáticas regulares a partir de modelos codificados como cadena de caracteres. En [2] Cook, Rosenfeld y Aronson introducen operaciones de inferencia que infieren gramáticas de contexto libre a partir de un conjunto finito de cadenas de caracteres. Radhakrishnan y Nagaraja [15] desarrolla un método para gramáticas regulares desde ejemplos positivos, los cuales forman una estructura de esqueleto. En [12] Jürgensen y Lindenmayer consideran modelos representados por estructuras árboreas que generan OL-Sistemas. En [11] Kreowski y Jeltsch desarrollan un algoritmo de inferencia basado en grafos. En [22, 23] Jeltsch, Rosales y Aguirre presentan TreeBaG, un sistema para generar y visualizar formas pictóricas.

• Materias:Herramientas de visualización Algoritmo de inferencia Módulos de software
• Subjects:Visualization tools Inference algorithm Software modules
• Palabras claves:Gramática de árboles, transductores, inferencia gramatical, sistema TreeBag.
• Keywords:Tree grammars, transducers, grammatical inference, TreeBag system.