Registro:
| Documento: | Tesis de Grado |
| Título: | Preservación de normalidad en transductores |
| Título alternativo: | Preservation of Normality in Transducers |
| Autor: | Orduna, Elisa |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2018 |
| Fecha en portada: | 19 de Julio 2018 |
| 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: | Carton, Olivier |
| Jurado: | Abriola, Sergio Alejandro; Figueira, Santiago Daniel |
| Idioma: | Inglés |
| Palabras clave: | ALEATORIEDAD; AUTOMATAS FINITOS; CADENAS DE MARKOV; NUMEROS NORMALESFINITE AUTOMATA; MARKOV CHAINS; NORMAL NUMBERS; RANDOMNESS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000628_Orduna |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000628_Orduna.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000628_Orduna |
| Ubicación: | Dep.COM 000628 |
| 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. Orduna, Elisa. (2018). Preservación de normalidad en transductores. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000628_Orduna |
Resumen:
En esta tesis se plantea el problema de determinar si un transductor finito determinístico arbitrario devuelve una palabra normal siempre que recibe como entrada una palabra normal, es decir, si preserva la normalidad. Una palabra infinita x es normal si todos los bloques de igual tamaño aparecen en x con la misma frecuencia asintótica. Trabajos anteriores caracterizan algunas familias de transductores que preservan normalidad: selectores de Agafonov, eliminación de todas las apariciones de un símbolo (en alfabetos con al menos tres símbolos), eliminación de finitos símbolos. Desarrollamos un algoritmo ideado por Olivier Carton que decide si un transductor determinístico preserva la normalidad. Lo hace además en tiempo polinomial. En primer lugar, el algoritmo obtiene una descomposición del transductor en componentes fuertemente conexas y analiza todas aquellas que sean recurrentes por separado. Para cada componente se construye un autómata con pesos que permite calcular la frecuencia de una palabra finita arbitraria en la salida, suponiendo que la entrada es una palabra normal. Por último, se verifica que estas frecuencias sean las esperadas, utilizando una implementación polinomial del algoritmo de Schüzenberger, propuesta por Crochemore. Además, presentamos un prototipo en Python que implementa el algoritmo.
Abstract:
In this thesis, we study the problem of deciding whether a given deterministic transducer outputs a normal word whenever it is fed with a normal word, in other words, whether it preserves normality or not. An infinite word x is normal if every block of the same length occurs in x with the same asymptotic frequency. Previous works characterize some families of transducers which preserve normality: Agafonov selectors, removal of all occurrences of a symbol (when alphabets contain at least three symbols), removal of a finite number of symbols. We develop an algorithm designed by Olivier Carton that decides if a given deterministic transducer preserves normality. Furthermore, this is done in polynomial time. First, the algorithm obtains a decomposition of the transducer into strongly connected components and analyzes those that are recurrent separately. For each component, it builds a weighted automaton, which allows it to determine the frequency of an arbitrary finite word in the output, assuming that the input is a normal word. Finally, it checks that these frequencies match the expected ones, using a polynomial implementation of Schützenberger’s algorithm, due to Crochemore. Additionally, we provide a prototype implementation in Python. Keywords: Finite Automata, Markov Chains, Normal Numbers, Randomness.
Citación:
---------- APA ----------
Orduna, Elisa. (2018). Preservación de normalidad en transductores. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000628_Orduna
---------- CHICAGO ----------
Orduna, Elisa. "Preservación de normalidad en transductores". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2018.https://hdl.handle.net/20.500.12110/seminario_nCOM000628_Orduna
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000628_Orduna.pdf
Distrubución geográfica
