Sobre as funções racionais multi-sequenciais
Resumo
Funções multi-sequenciais foram introduzidas por Choffrut e Schützenberger como a família das funções racionais cujo gráfico é uma união finita de funções sequenciais. Recentemente, Jeckert e Filiot mostraram que é decidível em tempo polinomial se uma função racional é multi-sequencial. Nesta comunicação estudamos as funções que são uma união de k funções sequenciais, para um inteiro fixo k. Apresentamos três caracterizações dessas funções, que recordam resultados clássicos sobre as relações racionais.
Referências
Béal, 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.
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. and Schützenberger, M. P. (1986). Décomposition de fonctions rationnelles. In STACS 86, volume 210 of Lecture Notes in Computer Science, pages 213–226. Springer.
Eilenberg, S. (1974). Automata, Languages, and Machines. Academic Press, Inc.
Jecker, I. and Filiot, E. (2015). Multi-sequential word relations. In DLT 2015, volume 9168 of Lecture Notes in Computer Science, pages 288–299. Springer.
Lombardy, S. and Sakarovitch, J. (2006). Sequential? Theoretical Computer Science, 356(1-2):224–244.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambridge University Press.
Sakarovitch, J. and de Souza, R. (2008). On the decidability of bounded valuedness for transducers. In MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 588–600. Springer.
Sakarovitch, J. and de Souza, R. (2010). Lexicographic decomposition of k-valued transducers. Theory of Computing Systems, 47(3):758–785.
Weber, A. (1996). Decomposing A k-valued transducer into k unambiguous ones. ITA, 30(5):379–413.
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. and Schützenberger, M. P. (1986). Décomposition de fonctions rationnelles. In STACS 86, volume 210 of Lecture Notes in Computer Science, pages 213–226. Springer.
Eilenberg, S. (1974). Automata, Languages, and Machines. Academic Press, Inc.
Jecker, I. and Filiot, E. (2015). Multi-sequential word relations. In DLT 2015, volume 9168 of Lecture Notes in Computer Science, pages 288–299. Springer.
Lombardy, S. and Sakarovitch, J. (2006). Sequential? Theoretical Computer Science, 356(1-2):224–244.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambridge University Press.
Sakarovitch, J. and de Souza, R. (2008). On the decidability of bounded valuedness for transducers. In MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 588–600. Springer.
Sakarovitch, J. and de Souza, R. (2010). Lexicographic decomposition of k-valued transducers. Theory of Computing Systems, 47(3):758–785.
Weber, A. (1996). Decomposing A k-valued transducer into k unambiguous ones. ITA, 30(5):379–413.
Publicado
26/07/2018
Como Citar
DE SOUZA, Rodrigo.
Sobre as funções racionais multi-sequenciais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 149-152.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3175.
