Autómatas arbóreos

Date
2022-04-20
Journal Title
Journal ISSN
Volume Title
Publisher
Benemérita Universidad Autónoma de Puebla
Abstract
"Los Autómatas de estado finito que procesan cadenas y arboles enraizados de símbolos apoyan una metodología parámetro fijo tratable (PFT) importante. Esta metodología es basada en la siguiente estrategia algorítmica de dos pasos; el primer paso consiste en calcular una representación para el grafo de ancho arbóreo acotado, como un árbol binario etiquetado, denominado árbol de análisis, para el objeto. En el segundo, se utiliza un autómata arbóreo de estado finito para reconocer con precisión los arboles de análisis que representan los objetos (por ejemplo, grafos de ancho arbóreo acotado) que tienen la propiedad de interés, por ejemplo, tener un ciclo Hamiltoniano. El presente documento abarca desde el estudio y presentación de los autómatas en su versión clásica hasta su versión arbórea, así como los resultados principales que nos conducen a los Teoremas de Courcelle y Bounlander".
Description
Keywords
Citation
Document Viewer
Select a file to preview:
Can't see the file? Try reloading