An algorithmic framework for disambiguation of finite automata
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En esta tesis, estudiamos la tarea de desambiguación de autómatas finitos, es decir, convertir un autómata en otro equivalente y no ambiguo. Para ello, desarrollamos un nuevo marco algorítmico que generaliza la determinizacion basada en construcción de subconjuntos y que cumple algunas propiedades deseables: (1) conserva el autómata original si este es no ambiguo, (2) calcula los estados sucesores sobre la marcha y (3) calcula cada nuevo estado en tiempo polinomial. A continuación, mostramos como aplicar este marco para la desambiguación parcial: cambiando el criterio que se utiliza para construir los nuevos estados, desarrollamos algoritmos para diferentes niveles de ambigüedad, es decir, autómatas finitamente ambiguos y polinomialmente ambiguos. Estos algoritmos también satisfacen las condiciones (1) para sus respectivos niveles de ambigüedad, así como (2) y (3). Por ultimo, extendemos el procedimiento de desambiguación a los autómatas con peso, para los mismos niveles de ambigüedad, conservando las propiedades anteriores. El autómata resultante no siempre es finito, por lo que nos centramos en los autómatas sobre el semianillo tropical y presentamos algunas condiciones simples para garantizar la finitud en ese caso.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2025.
Keywords
Teoría de autómatas algorítmica, Modelos de autómatas no ambiguos, Grado de ambigüedad, Determinización, Desambiguación, Autómatas con peso