Abstract
Weakly and strongly quasiperiodic morphisms are tools introduced to study quasiperiodic words. Formally they map respectively at least one or any non-quasiperiodic word to a quasiperiodic word. Considering them both on finite and infinite words, we get four families of morphisms between which we study relations. We provide algorithms to decide whether a morphism is strongly quasiperiodic on finite words or on infinite words.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Apostolico, A., Ehrenfeucht, A.: Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119, 247–265 (1993)
Berstel, J., Séébold, P.: Sturmian words. In: Lothaire, M. (ed.) Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90, pp. 45–110. Cambridge University Press (2002)
Brodal, G.S., Pedersen, C.N.S.: Finding maximal quasiperiodicities in strings. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 397–411. Springer, Heidelberg (2000)
Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16, 109–114 (1965)
Glen, A., Levé, F., Richomme, G.: Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409(3), 578–600 (2008)
Groult, R., Richomme, G.: Optimality of some algorithms to detect quasiperiodicities. Theoret. Comput. Sci. 411, 3110–3122 (2010)
Iliopoulos, C.S., Mouchard, L.: Quasiperiodicity: from detection to normal forms. Journal of Automata, Languages and Combinatorics 4(3), 213–228 (1999)
Lentin, A., Schützenberger, M.P.: A combinatorial problem in the theory of free monoids. In: Bose, R.C., Dowling, T.W. (eds.) Combinatorial Mathematics and its Applications, pp. 128–144. Univ. North Carolina Press (1969)
Levé, F., Richomme, G.: Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 84, 128–238 (2004)
Levé, F., Richomme, G.: Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372(1), 15–25 (2007)
Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 17. Addison-Wesley (1983); Reprinted in the Cambridge Mathematical Library. Cambridge University Press, UK (1997)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press (2002)
Lyndon, R.C., Schützenberger, M.-P.: The equation a m = b n c p in a free group. Michigan Math. J. 9, 289–298 (1962)
Marcus, S.: Quasiperiodic infinite words. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 82, 170–174 (2004)
Marcus, S., Monteil, T.: Quasiperiodic infinite words: multi-scale case and dynamical properties. Technical Report arXiv:math/0603354, arxiv.org (2006)
Richomme, G.: Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10(5), 761–786 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levé, F., Richomme, G. (2013). On Quasiperiodic Morphisms. In: Karhumäki, J., Lepistö, A., Zamboni, L. (eds) Combinatorics on Words. Lecture Notes in Computer Science, vol 8079. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40579-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-40579-2_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40578-5
Online ISBN: 978-3-642-40579-2
eBook Packages: Computer ScienceComputer Science (R0)