DOI

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.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory
Подзаголовок основной публикации25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
РедакторыNelma Moreira, Rogério Reis
ИздательSpringer Nature
Страницы267-278
Число страниц12
ISBN (печатное издание)9783030815073
DOI
СостояниеОпубликовано - 2021
Событие25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Продолжительность: 16 авг 202120 авг 2021

Серия публикаций

НазваниеLecture Notes in Computer Science
Том12811 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция25th International Conference on Developments in Language Theory, DLT 2021
ГородVirtual, Online
Период16/08/2120/08/21

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 86499356