Sobre a minimização de transdutores sequenciais
Resumo
Estudamos a minimização de transdutores sequenciais utilizando para as saídas uma família de monóides que chamamos de monóides com mdc. Provamos a existência de um transdutor minimal para funções sequenciais ∑* → M, onde M é um monóide cancelativo com mdc único. Esse resultado inclui diversos monóides de interesse, como os monóides livres, e o monóide aditivo dos números reais não-negativos. Também apresentamos uma caracterização das funções sequenciais ∑* → M, onde M é um monóide cancelativo com mdc, utilizando a congruência à direita de uma função.
Referências
B´eal, M. P., Carton, O., Prieur, C., and Sakarovitch, J. (2003). Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theoretical Computer Science, 292(1):45–63.
Benesty, J., Sondhi, M., and Huang, Y., editors (2008). Springer Handbook of Speech Processing. Springer-Verlag Berlin Heidelberg.
Choffrut, C. (1979). A generalization of Ginsburg and Rose’s characterization of gsm mappings. In ICALP’79, volume 71 of Lecture Notes in Computer Science, pages 88–103. Springer-Verlag.
Choffrut, C. (2003). Minimizing subsequential transducers: A survey. Theoretical Computer Science, 292(1):131–143.
de Souza, R. (2004). Propriedades de algumas classes de relações racionais. Master’s thesis, Instituto de Matemática e Estatística, Universidade de São Paulo.
Eilenberg, S. (1974). Automata, Languages, and Machines. Academic Press.
Lombardy, S. and Sakarovitch, J. (2006). Sequential? Theoretical Computer Science, 356(1-2):224–244.
Mohri, M. (2000). Minimization algorithms for sequential transducers. Theoretical Computer Science, 234(1-2):177–201.
Reutenauer, C. (1990). Subsquential functions: Characterizations, minimization, examples. In International Meeting of Young Computer Scientists, volume 464 of Lecture
Notes in Computer Science, pages 62–79.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambridge University Press.
Schutzenberger, M. P. (1977). Sur une variante des fonctions sequentielles. Theoretical Computer Science, 4(1):47–57.
Benesty, J., Sondhi, M., and Huang, Y., editors (2008). Springer Handbook of Speech Processing. Springer-Verlag Berlin Heidelberg.
Choffrut, C. (1979). A generalization of Ginsburg and Rose’s characterization of gsm mappings. In ICALP’79, volume 71 of Lecture Notes in Computer Science, pages 88–103. Springer-Verlag.
Choffrut, C. (2003). Minimizing subsequential transducers: A survey. Theoretical Computer Science, 292(1):131–143.
de Souza, R. (2004). Propriedades de algumas classes de relações racionais. Master’s thesis, Instituto de Matemática e Estatística, Universidade de São Paulo.
Eilenberg, S. (1974). Automata, Languages, and Machines. Academic Press.
Lombardy, S. and Sakarovitch, J. (2006). Sequential? Theoretical Computer Science, 356(1-2):224–244.
Mohri, M. (2000). Minimization algorithms for sequential transducers. Theoretical Computer Science, 234(1-2):177–201.
Reutenauer, C. (1990). Subsquential functions: Characterizations, minimization, examples. In International Meeting of Young Computer Scientists, volume 464 of Lecture
Notes in Computer Science, pages 62–79.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambridge University Press.
Schutzenberger, M. P. (1977). Sur une variante des fonctions sequentielles. Theoretical Computer Science, 4(1):47–57.
Publicado
04/07/2016
Como Citar
DE SOUZA, Rodrigo.
Sobre a minimização de transdutores sequenciais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 840-843.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9838.
