On Substitutions Preserving Their Return Sets | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Substitutions Preserving Their Return Sets

  • Conference paper
  • First Online:
Combinatorics on Words (WORDS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13899))

Included in the following conference series:

Abstract

We consider the question of whether or not a given primitive substitution preserves its sets of return words—or return sets for short. More precisely, we study the property asking that the image of the return set to a word equals the return set to the image of that word. We show that, for bifix encodings (where images of letters form a bifix code), this property holds for all but finitely many words. On the other hand, we also show that every conjugacy class of Sturmian substitutions contains a member for which the property fails infinitely often. Various applications and examples of these results are presented, including a description of the subgroups generated by the return sets in the shift of the Thue–Morse substitution. Up to conjugacy, these subgroups can be sorted into strictly decreasing chains of isomorphic subgroups weaving together a simple pattern. This is in stark contrast with the Sturmian case, and more generally with the dendric case (including in particular the Arnoux–Rauzy case), where it is known that all return sets generate the free group over the underlying alphabet.

This work was supported by the Agence Nationale de la Recherche through the project “Codys” (ANR-18-CE40-0007).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8579
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10724
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Almeida, J.: Profinite groups associated with weakly primitive substitutions. J. Math. Sci. 144(2), 3881–3903 (2007). https://doi.org/10.1007/s10958-007-0242-y, translated from Fundam. Prikl. Mat., 11(3), 13–48 (2005)

  2. Almeida, J., Costa, A.: Presentations of Schützenberger groups of minimal subshifts. Israel J. Math. 196(1), 1–31 (2013). https://doi.org/10.1007/s11856-012-0139-4

    Article  MathSciNet  MATH  Google Scholar 

  3. Almeida, J., Costa, A.: A geometric interpretation of the Schützenberger group of a minimal subshift. Ark. Math. 54(2), 243–275 (2016). https://doi.org/10.1007/s11512-016-0233-7

    Article  MATH  Google Scholar 

  4. Balková, L., Pelantová, E., Steiner, W.: Sequences with constant number of return words. Monatsh. Math. 155(3–4), 251–263 (2008). https://doi.org/10.1007/s00605-008-0001-2

    Article  MathSciNet  MATH  Google Scholar 

  5. Berstel, J., Séébold, P.: A remark on morphic Sturmian words. RAIRO - Theor. Inform. Appl. 28(3–4), 255–263 (1994). https://doi.org/10.1051/ita/1994283-402551

    Article  MathSciNet  MATH  Google Scholar 

  6. Berstel, J., De Felice, C., Perrin, D., Reutenauer, C., Rindone, G.: Bifix codes and Sturmian words. J. Algebra 369, 146–202 (2012). https://doi.org/10.1016/j.jalgebra.2012.07.013

    Article  MathSciNet  MATH  Google Scholar 

  7. Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press (2009). https://doi.org/10.1017/cbo9781139195768

  8. Berstel, J., Séébold, P.: A characterization of Sturmian morphisms. In: Borzyszkowski, A., Sokołowski, S. (eds.) Lecture Notes in Computer Science, vol. 711, pp. 281–290. Springer, Berlin Heidelberg (1993). https://doi.org/10.1007/3-540-57182-5_20

  9. Berthé, V., Dolce, F., Durand, F., Leroy, J., Perrin, D.: Rigidity and substitutive dendric words. Int. J. Found. Comput. 29(05), 705–720 (2018). https://doi.org/10.1142/S0129054118420017

    Article  MathSciNet  MATH  Google Scholar 

  10. Berthé, V., et al.: Acyclic, connected and tree sets. Monatsh. Math. 176(4), 521–550 (2015). https://doi.org/10.1007/s00605-014-0721-4

    Article  MathSciNet  MATH  Google Scholar 

  11. Berthé, V., et al.: Maximal bifix decoding. Discrete Math. 338(5), 725–742 (2015). https://doi.org/10.1016/j.disc.2014.12.010

    Article  MathSciNet  MATH  Google Scholar 

  12. Costa, A.: Conjugacy invariants of subshifts: An approach from profinite semigroup theory. Int. J. Algebra Comput. 16(4), 629–655 (2006). https://doi.org/10.1142/s0218196706003232

    Article  MathSciNet  MATH  Google Scholar 

  13. Durand, F.: A generalization of Cobham’s theorem. Theoret. Comput. Sci. 31(2), 169–185 (1998). https://doi.org/10.1007/s002240000084

    Article  MathSciNet  MATH  Google Scholar 

  14. Durand, F.: A characterization of substitutive sequences using return words. Discrete Math. 179(1–3), 89–101 (1998). https://doi.org/10.1016/S0012-365X(97)00029-0

    Article  MathSciNet  MATH  Google Scholar 

  15. Durand, F., Host, B., Skau, C.: Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergod. Theory Dyn. Syst. 19(4), 953–993 (1999). https://doi.org/10.1017/S0143385799133947

    Article  MathSciNet  MATH  Google Scholar 

  16. Durand, F., Leroy, J.: The constant of recognizability is computable for primitive morphisms. J. Integer S. 20 (2017)

    Google Scholar 

  17. Durand, F., Perrin, D.: Dimension Groups and Dynamical Systems. Cambridge Studies in Advanced Mathematics, Cambridge University Press (2022). https://doi.org/10.1017/9781108976039

  18. Goulet-Ouellet, H.: Pronilpotent quotients associated with primitive substitutions. J. Algebra 606, 341–370 (2022). https://doi.org/10.1016/j.jalgebra.2022.05.021

    Article  MathSciNet  MATH  Google Scholar 

  19. Goulet-Ouellet, H.: Suffix-connected languages. Theoret. Comput. Sci. 923, 126–143 (2022). https://doi.org/10.1016/j.tcs.2022.05.001

    Article  MathSciNet  MATH  Google Scholar 

  20. Kapovich, I., Myasnikov, A.: Stallings foldings and subgroups of free groups. J. Algebra 248(2), 608–668 (2002). https://doi.org/10.1006/jabr.2001.9033

    Article  MathSciNet  MATH  Google Scholar 

  21. Klouda, K.: Bispecial factors in circular non-pushy D0L languages. Theoret. Comput. Sci. 445, 63–74 (2012). https://doi.org/10.1016/j.tcs.2012.05.007

    Article  MathSciNet  MATH  Google Scholar 

  22. Kyriakoglou, R.: Iterated morphisms, combinatorics on words and symbolic dynamical systems. Ph.D. thesis, Université Paris-Est (2019)

    Google Scholar 

  23. Lothaire, M.: Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002). https://doi.org/10.1017/CBO9781107326019

  24. de Luca, A., Mione, L.: On bispecial factors of the Thue-Morse word. Inf. Process. Lett. 49(4), 179–183 (1994). https://doi.org/10.1016/0020-0190(94)90008-6

    Article  MathSciNet  MATH  Google Scholar 

  25. Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Berlin Heidelberg (2001). https://doi.org/10.1007/978-3-642-61896-3

  26. Mignosi, F., Séébold, P.: Morphismes sturmiens et règles de Rauzy. J. Théor. Nr. Bordx. 5(2), 221–233 (1993). https://doi.org/10.5802/jtnb.91

    Article  MATH  Google Scholar 

  27. Mossé, B.: Puissance de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci. 99(2), 327–334 (1992). https://doi.org/10.1016/0304-3975(92)90357-L

    Article  MathSciNet  MATH  Google Scholar 

  28. Queffélec, M.: Substitution dynamical systems–spectral analysis, Lecture Notes in Mathematics, vol. 1294. Springer-Verlag, Berlin, second edn. (2010). https://doi.org/10.1007/978-3-642-11212-6

  29. Séébold, P.: On the conjugation of standard morphisms. Theoret. Comput. Sci. 195(1), 91–109 (1998). https://doi.org/10.1016/s0304-3975(97)00159-x

    Article  MathSciNet  MATH  Google Scholar 

  30. Touikan, N.W.M.: A fast algorithm for Stallings’ folding process. Int. J. Algebra Comput. 16(6), 1031–1045 (2006). https://doi.org/10.1142/S0218196706003396

    Article  MathSciNet  MATH  Google Scholar 

  31. Vuillon, L.: A characterization of Sturmian words by return words. Europ. J. Comb. 22(2), 263–275 (2001). https://doi.org/10.1006/eujc.2000.0444

    Article  MathSciNet  MATH  Google Scholar 

  32. Wen, Z.X., Wen, Z.Y.: Local isomorphisms of the invertible substitutions. C. R. Acad. Sci. Paris 318, 299–304 (1994)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IRIF, Université Paris Cité, 75013, Paris, France

    Valérie Berthé & Herman Goulet-Ouellet

Authors
  1. Valérie Berthé
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Herman Goulet-Ouellet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Herman Goulet-Ouellet .

Editor information

Editors and Affiliations

  1. Aix-Marseille University, Marseille, France

    Anna Frid

  2. Loughborough University, Loughborough, UK

    Robert Mercaş

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Berthé, V., Goulet-Ouellet, H. (2023). On Substitutions Preserving Their Return Sets. In: Frid, A., Mercaş, R. (eds) Combinatorics on Words. WORDS 2023. Lecture Notes in Computer Science, vol 13899. Springer, Cham. https://doi.org/10.1007/978-3-031-33180-0_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-33180-0_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-33179-4

  • Online ISBN: 978-3-031-33180-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation