Teoría de transductores finitos

Breve resumen de la materia

Los autómatas finitos son el modelo más simple de computación. Constituyen el primer nivel en cualquier jerarquía de máquinas de Turing con más o menos restricciones. Cuando los autómatas finitos se enriquecen con la noción de salida, forman un modelo lo suficientemente potente como para expresar propiedades más complejas.
Independientemente de su papel en el estudio teórico de los lenguajes formales, estos autómatas son herramientas útiles para el análisis sintáctico de lenguajes de programación,
así como para el procesamiento de lenguaje natural, análisis fonológico o morfológico, aritmética computacional y teoría de números. En este curso se presenta el modelo de
transductores finitos y sus diversas subfamilias, y se estudian las relaciones que realizan los transductores finitos.

Objetivos del curso

El objetivo del curso es comprender los fundamentos teóricos de los autómatas finitos y en particular de la extensión con una noción de salida (transductores finitos).

Programa

– Autómatas finitos. Expresiones regulares. Lenguajes regulares.
– Transductores finitos. Relaciones realizadas por transductores finitos. Racionalidad y composición. Problema de la correspondencia de Post. Indecidibilidad de la equivalencia.
– Morfismos y cobertura de transductores. Propiedades locales de morfismos. Bisimulación.
Cobertura de Schützenberger.
– Transductores y relaciones síncronas. Determinización y complementación. Composición.
– Transductores en tiempo real. Segundo teorema de composición. Uniformización de
relaciones racionales. Relaciones racionales funcionales.
– Transductores secuenciales. Decidibilidad de la secuencialidad. Secuencialización.
Minimización de transductores secuenciales. Funciones secuenciales. Relaciones racionales funcionales.

Prerrequisitos

Conocimientos básicos de autómatas finitos y teoría de lenguajes formales.

Bibliografía
– Jacques Sakarovitch, Elements of Automata Theory, Cambridge University Press, 2009
– Tero Harju, Juhani Karhumäki, Finite transducers and rational transductions, in Handbook
of Finite Automata, J.-É. Pin ed., EMS Press 2021.
– Lombardy, Sylvain, Jacques Sakarovitch. «Morphisms and minimisation of weighted automata.» Fundamenta Informaticae 186 (2022).
– Bonchi, Filippo, Damien Pous. «Hacking nondeterminism with induction and coinduction.»
Communications of the ACM 58.2 (2015): 87-95.
– Balle, Borja, Prakash Panangaden, Doina Precup. «Singular value automata and
approximate minimization.» Mathematical Structures in Computer Science 29.9 (2019): 1444-1478.
– Cadilhac, Michaël, Olivier Carton, Charles Paperman. «Continuity of functional transducers:
a profinite study of rational functions.» Logical Methods in Computer Science 16 (2020).
– Carton, Olivier, Elisa Orduna. «Preservation of normality by transducers.» Information and Computation 282 (2022): 104650.
– Lombardy, Sylvain, Jacques Sakarovitch. «Two Routes to Automata Minimization and the Ways to Reach It Efficiently.» Implementation and Application of Automata: 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30–August 2, 2018, Proceedings 23. Springer International Publishing, 2018.
– Demaille, Akim, et al. «A type system for weighted automata and rational expressions.»
International Conference on Implementation and Application of Automata. Cham: Springer
International Publishing, 2014.
– Demaille, Akim. «Derived-term automata of multitape expressions with composition.»
Scientific Annals of Computer Science 27.2 (2017): 137-176.
– Maneth, Sebastian, Helmut Seidl, Martin Vu. «Definability results for top-down tree
transducers.» International Journal of Foundations of Computer Science 34.02n03 (2023):
253-287.
– Löbel, Raphaela, Michael Luttenberger, Helmut Seidl. «On the balancedness of
tree-to-word transducers.» International Journal of Foundations of Computer Science 32.06
(2021): 761-783.