An algorithmic framework for disambiguation of finite automata

Simple item page
dc.catalogadorgjm
dc.contributor.advisorRiveros Jaeger, Cristian
dc.contributor.authorCari, Mauricio
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2026-01-20T14:40:37Z
dc.date.available2026-01-20T14:40:37Z
dc.date.issued2025
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2025.
dc.description.abstractEn 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.
dc.fechaingreso.objetodigital2026-01-20
dc.format.extentix, 70 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/tesisUC/ING/107781
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/107781
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/107781
dc.information.autorucEscuela de Ingeniería; Riveros Jaeger, Cristian; 0000-0003-0832-116X; 131276
dc.information.autorucEscuela de Ingeniería; Cari, Mauricio; S/I; 1087141
dc.language.isoen
dc.nota.accesocontenido completo
dc.rightsacceso abierto
dc.subjectTeoría de autómatas algorítmica
dc.subjectModelos de autómatas no ambiguos
dc.subjectGrado de ambigüedad
dc.subjectDeterminización
dc.subjectDesambiguación
dc.subjectAutómatas con peso
dc.subject.ddc600
dc.titleAn algorithmic framework for disambiguation of finite automata
dc.typetesis de maestría
sipa.codpersvinculados131276
sipa.codpersvinculados1087141
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS_MCari.pdf
Size:
788.54 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ING Tesis magíster