Sobre a decomposição de um transdutor bidirecional finitamente valorado
Resumo
A possibilidade de se decompor um transdutor bidirecional k-valorado T em k transdutores bidirecionais funcionais é um problema em aberto. Consideramos dois casos particulares desse problema: aquele em que T é k-ambíguo na entrada, e aquele em que imagens distintas de uma mesma palavra pela relação realizada por T têm comprimentos distintos. Discutimos como essas decomposições podem ser obtidas utilizando construções que apresentamos para resolver outros problemas: decompor um transdutor unidirecional k-valorado, e construir uma uniformização de um transdutor bidirecional.
Palavras-chave:
transdutor bidirecional, transdutor finitamente valorado, revestimento de autômatos
Referências
de Souza, R. (2013). Uniformisation of two-way transducers. In Language and Automata Theory and Applications - LATA 2013. Lecture Notes in Computer Science, volume 7810, pages 547–558. Springer, Berlin.
Engelfriet, J. and Hoogeboom, H. (2001). MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2(2):216–254.
Guillon, B. (2016). Input- or output-unary sweeping transducers are weaker than their 2-way counterparts. RAIRO - Theoretical Informatics and Applications, 50(4):275–294.
Hopcroft, J. E. and Ullman, J. D. (1967). An approach to a unified theory of automata. In 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), pages 140–147. IEEE Computer Society.
Mihov, S. and Schulz, K. U. (2019). Finite-state techniques: automata, transducers and bimachines. Cambridge University Press.
Muscholl, A. (2017). A Tour of Recent Results on Word Transducers. In Fundamentals of Computation Theory. FCT 2017, pages 29–33.
Muscholl, A. and Puppis, G. (2019). The many facets of string transducers. In Leibniz International Proceedings in Informatics, LIPIcs, volume 126. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
Rabin, M. O. and Scott, D. (1959). Finite Automata and Their Decision Problems. IBM Journal of Research and Development, 3(2):114–125.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambdrige University Press.
Sakarovitch, J. and de Souza, R. (2010). Lexicographic Decomposition of k-Valued Transducers. Theory of Computing Systems, 47(3):758–785.
Shepherdson, J. C. (1959). The reduction of two-way automata to one-way automata. IBM J. Res. Dev., 3:198–200.
Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. RAIRO- Theoretical Informatics and Applications, 30(5):379–413.
Engelfriet, J. and Hoogeboom, H. (2001). MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2(2):216–254.
Guillon, B. (2016). Input- or output-unary sweeping transducers are weaker than their 2-way counterparts. RAIRO - Theoretical Informatics and Applications, 50(4):275–294.
Hopcroft, J. E. and Ullman, J. D. (1967). An approach to a unified theory of automata. In 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), pages 140–147. IEEE Computer Society.
Mihov, S. and Schulz, K. U. (2019). Finite-state techniques: automata, transducers and bimachines. Cambridge University Press.
Muscholl, A. (2017). A Tour of Recent Results on Word Transducers. In Fundamentals of Computation Theory. FCT 2017, pages 29–33.
Muscholl, A. and Puppis, G. (2019). The many facets of string transducers. In Leibniz International Proceedings in Informatics, LIPIcs, volume 126. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
Rabin, M. O. and Scott, D. (1959). Finite Automata and Their Decision Problems. IBM Journal of Research and Development, 3(2):114–125.
Sakarovitch, J. (2009). Elements of Automata Theory. Cambdrige University Press.
Sakarovitch, J. and de Souza, R. (2010). Lexicographic Decomposition of k-Valued Transducers. Theory of Computing Systems, 47(3):758–785.
Shepherdson, J. C. (1959). The reduction of two-way automata to one-way automata. IBM J. Res. Dev., 3:198–200.
Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. RAIRO- Theoretical Informatics and Applications, 30(5):379–413.
Publicado
30/06/2020
Como Citar
DE SOUZA, Rodrigo.
Sobre a decomposição de um transdutor bidirecional finitamente valorado. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 73-76.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11093.
