Abstract
We present here the notion of breadth-first signature of trees and of prefix-closed languages; and its relationship with numeration system theory. A signature is the serialisation into an infinite word of an ordered infinite tree of finite degree. Using a known construction from numeration system theory, we prove that the signature of (prefix-closed) rational languages are substitutive words and conversely that a special subclass of substitutive words define (prefix-closed) rational languages.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Akiyama, S., Frougny, C., Sakarovitch, J.: Powers of rationals modulo 1 and rational base number systems. Israel J. Math. 168, 53–91 (2008)
Marsault, V., Sakarovitch, J.: Rhythmic generation of infinite trees and languages (2014), In preparation, early version accessible at arXiv:1403.5190
Rigo, M., Maes, A.: More on generalized automatic sequences. Journal of Automata, Languages and Combinatorics 7(3), 351–376 (2002)
Dumont, J.M., Thomas, A.: Systèmes de numŕation et fonctions fractales relatifs aux substitutions. Theor. Comput. Sci. 65(2), 153–169 (1989)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972)
Diestel, R.: Graph Theory. Springer (1997)
Lecomte, P., Rigo, M.: Numeration systems on a regular language. Theory Comput. Syst. 34, 27–44 (2001)
Lecomte, P., Rigo, M.: Abstract numeration systems. In: Berthé, V., Rigo, M. (eds.) Combinatorics, Automata and Number Theory, pp. 108–162. Cambridge Univ. Press (2010)
Berthé, V., Rigo, M.: Combinatorics, Automata and Number Theory. Cambridge University Press (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Marsault, V., Sakarovitch, J. (2014). Breadth-First Serialisation of Trees and Rational Languages. In: Shur, A.M., Volkov, M.V. (eds) Developments in Language Theory. DLT 2014. Lecture Notes in Computer Science, vol 8633. Springer, Cham. https://doi.org/10.1007/978-3-319-09698-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-09698-8_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09697-1
Online ISBN: 978-3-319-09698-8
eBook Packages: Computer ScienceComputer Science (R0)