In this paper we introduce a new notion of a symmetry group of an infinite word. Given a subgroup Gn of the symmetric group Sn, it acts on the set of finite words of length n by permutation. For each n, a symmetry group of an infinite word w is a subgroup Gn of the symmetric group Sn such that g(v) is a factor of w for each permutation g∈ Gn and each factor v of w. We study general properties of symmetry groups of infinite words and characterize symmetry groups of several families of infinite words. We show that symmetry groups of Sturmian words and more generally Arnoux-Rauzy words are of order two for large enough n; on the other hand, symmetry groups of certain Toeplitz words have exponential growth.

Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
EditorsNelma Moreira, Rogério Reis
PublisherSpringer Nature
Pages267-278
Number of pages12
ISBN (Print)9783030815073
DOIs
StatePublished - 2021
Event25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science
Volume12811 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Developments in Language Theory, DLT 2021
CityVirtual, Online
Period16/08/2120/08/21

    Research areas

  • Arnoux-Rauzy words, Infinite words, Symmetry groups, Toeplitz words

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 86499356