On the decomposition of a finite-valued two-way transducer
Abstract
The possibility of decomposing a k-valued two-way transducer T on k functional two-way transducers is an open problem. We consider two particular cases of this problem: the one where T is input k-ambiguous, and the case where distinct images of every input word, by the relation realised by T, have different lengths. We discuss how these decompositions can be obtained using constructions that we have presented to solve other problems: the decomposition of a k-valued transducer, and the construction of an uniformisation of a two-way transducer.
Keywords:
two-way transducer, finite-valued transducer, covering of automata
References
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.
Published
2020-06-30
How to Cite
DE SOUZA, Rodrigo.
On the decomposition of a finite-valued two-way transducer. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
