Registro:
| Documento: | Tesis de Grado |
| Título: | Clausura conmutativa de lenguajes regulares |
| Título alternativo: | Commutative closure of regular languages |
| Autor: | Lew Deveali, Simón |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2024-12-03 |
| Fecha en portada: | 2024 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Becher, Verónica Andrea |
| Director Asistente: | Mollo Cunningham, Ignacio Agustín |
| Jurado: | Abriola, Sergio Alejandro; Braberman, Víctor Adrián |
| Idioma: | Español |
| Palabras clave: | LENGUAJES REGULARES; CLAUSURA CONMUTATIVA; AUTOMATAS; MONOIDE LIBRE CONMUTATIVO; CONJUNTOS RECONOCIBLESREGULAR LANGUAGES; COMMUTATIVE CLOSURE; AUTOMATA; FREE COMMUTATIVE MONOID; RECOGNISABLE SETS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000817_LewDeveali |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000817_LewDeveali.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000817_LewDeveali |
| Ubicación: | Dep.COM 000817 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Lew Deveali, Simón. (2024). Clausura conmutativa de lenguajes regulares. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000817_LewDeveali |
Resumen:
Consideremos un alfabeto finito A y A*, el monoide libre generado por el alfabeto con la operación de concatenación. Dos palabras comparten su imagen conmutativa cuando una es permutación de los símbolos de la otra palabra. La clausura conmutativa de un lenguaje L ⊆ A* es el conjunto C(L) ⊆ A* de palabras cuya imagen conmutativa coincide con la de alguna palabra en L. Damos un algoritmo que, dado un lenguaje regular L, produce el autómata finito determinístico que acepta la clausura conmutativa C(L) siempre que ésta sea regular. El problema de decidir si C(L) es regular ya fue resuelto por Ginsburg y Spanier en 1966 utilizando la decibilidad de las sentencias de Presburger, y por Gohon en 1985 proponiendo un algoritmo mas simple basado en series formales. Sin embargo, hasta la fecha la literatura no tiene un algoritmo que en todos los casos positivos construya un autómata o una expresión regular que acepte C(L). Este es el principal aporte de nuestro trabajo.
Abstract:
Let us consider a finite alphabet A and A*, the free monoid generated by the alphabet with the concatenation operation. Two words share their commutative image when one is a permutation of the symbols of the other word. The commutative closure of a language L ⊆ A* is the set C(L) ⊆ A* of words whose commutative image coincides with that of some word in L. We provide an algorithm that, given a regular language L, produces the deterministic finite automaton that accepts the commutative closure C(L), provided that this closure is regular. The problem of deciding whether C(L) is regular was already solved by Ginsburg and Spanier in 1966 using the decidability of Presburger sentences, and by Gohon in 1985 with a simpler algorithm based on formal power series. However, to date, the literature does not contain an algorithm that, in all positive cases, constructs an automaton or a regular expression that accepts C(L). This is the main contribution of our work.
Citación:
---------- APA ----------
Lew Deveali, Simón. (2024). Clausura conmutativa de lenguajes regulares. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000817_LewDeveali
---------- CHICAGO ----------
Lew Deveali, Simón. "Clausura conmutativa de lenguajes regulares". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2024.https://hdl.handle.net/20.500.12110/seminario_nCOM000817_LewDeveali
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000817_LewDeveali.pdf
Distrubución geográfica
