Abstract
There exist many constructions of infinite words over three-letter alphabet avoiding squares. However, the characterization of the lexicographically minimal square-free word is an open problem. Efficient construction of this word is not known. We show that the situation changes when some letters commute with each other. We give two characterizations (morphic and recursive) of the lexicographically minimal square-free word \(\widetilde{\mathbf {v}}\) in the case of a partially commutative alphabet \(\Theta \) of size three. We consider the only non-trivial relation of partial commutativity, for which \(\widetilde{\mathbf {v}}\) exists: there are two commuting letters, while the third one is blocking (does not commute at all). We also show that the \(n\)-th letter of \(\widetilde{\mathbf {v}}\) can be computed in time logarithmic with respect to \(n\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Commutation Relation
- Combinatorial Structure
- Neutral Element
- Concatenation Operation
- Recurrent Procedure
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
Allouche, J., Currie, J.D., Shallit, J.: Extremal infinite overlap-free binary words. Electr. J. Comb. 5 (1998)
Allouche, J., Shallit, J.O.: Automatic Sequences - Theory, Applications, Generalizations. Cambridge University Press (2003)
Berstel, J.: A rewriting of Fife’s theorem about overlap-free words. In: Karhumäki, J., Maurer, H., Rozenberg, G. (eds.) Results and Trends in Theoretical Computer Science, pp. 19–29. Springer, Heidelberg (1994)
Berstel, J.: Axel Thue’s work on repetitions in words. Séries formelles et combinatoire algébrique 11, 65–80 (1992)
Brandenburg, F.J.: Uniformly growing \(k\)-th power-free homomorphisms. Theoretical Computer Science 23(1), 69–82 (1983)
Carpi, A.: On the number of abelian square-free words on four letters. Discrete Applied Mathematics 81(1–3), 155–167 (1998)
Carpi, A.: On abelian squares and substitutions. Theoretical Computer Science 218(1), 61–81 (1999)
Carpi, A., de Luca, A.: Square-free words on partially commutative free monoids. Information Processing Letters 22(3), 125–131 (1986)
Cartier, P., Foata, D.: Problèmes combinatoires de commutation et réarrangements. LNM, vol. 85. Springer, Heidelberg (1969)
Cori, R., Formisano, M.R.: ITA. Partially abelian squarefree words 24, 509–520 (1990)
Cori, R., Formisano, M.R.: On the number of partially abelian square-free words on a three-letter alphabet. Theoretical Computer Science 81(1), 147–153 (1991)
Currie, J.D.: On the structure and extendibility of k-power free words. European Journal of Combinatorics 16(2), 111–124 (1995)
Erdös, P.: Some unsolved problems. Magyar Tud. Akad. Mat. Kutató 6, 221–254 (1961)
Evdokimov, A.: Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk. SSSR 179, 1268–1271 (1968)
Keränen, V.: Abelian squares are avoidable on 4 letters. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623. Springer, Heidelberg (1992)
Lothaire : Algebraic Combinatorics on Words. Encyclopedia of mathematics and its application, vol. 90. Cambridge University Press (2002)
Mikulski, Ł., Piątkowski, M., Rytter, W.: Square-free words over partially commutative alphabets. CS-TR 1439, Newcstle University (2014)
Pleasants, P.A.B.: Non-repetitive sequences. Mathematical Proceedings of the Cambridge Philosophical Society 68, 267–274 (1970)
Thue, A.: Über unendliche Zeichenreihen. Videnskabsselskabets Skrifter, I Mat.-nat. K1, 1–22 (1906)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Mikulski, Ł., Piątkowski, M., Rytter, W. (2015). Square-Free Words over Partially Commutative Alphabets. In: Dediu, AH., Formenti, E., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2015. Lecture Notes in Computer Science(), vol 8977. Springer, Cham. https://doi.org/10.1007/978-3-319-15579-1_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-15579-1_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15578-4
Online ISBN: 978-3-319-15579-1
eBook Packages: Computer ScienceComputer Science (R0)