On multi-sequential rational functions

• Rodrigo de Souza UFRPE

DOI: https://doi.org/10.5753/etc.2018.3175

Abstract

Multi-sequential functions were introduced by Choffrut and Schützenberger as the family of rational functions whose graph is a finite union of sequential functions. Recently, Jeckert and Filiot have shown that it is decidable in polynomial time if a rational function is multi-sequential. In this communication we study the rational functions that are a union of k sequential functions, for a fixed integer k. We present three characterizations of these functions, which are related to classical results of the theory of rational relations.

References

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.