Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 language | English |
---|---|
Title of host publication | Developments in Language Theory |
Subtitle of host publication | 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings |
Editors | Nelma Moreira, Rogério Reis |
Publisher | Springer Nature |
Pages | 267-278 |
Number of pages | 12 |
ISBN (Print) | 9783030815073 |
DOIs | |
State | Published - 2021 |
Event | 25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online Duration: 16 Aug 2021 → 20 Aug 2021 |
Name | Lecture Notes in Computer Science |
---|---|
Volume | 12811 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 25th International Conference on Developments in Language Theory, DLT 2021 |
---|---|
City | Virtual, Online |
Period | 16/08/21 → 20/08/21 |
ID: 86499356