The finite index basis property

Valérie Berthé ^[4] ; Clelia De Felice ^[1] ; Francesco Dolce ^[5] ; Julien Leroy ^[2] ; Dominique Perrin ^[5] ; Christophe Reutenauer ^[3] ; Giuseppina Rindone ^[5]
1. [1] University of Salerno
  
  University of Salerno
  
  Fisciano, Italia
2. [2] University of Luxembourg
  
  University of Luxembourg
  
  Luxemburgo
3. [3] University of Quebec at Montreal
  
  University of Quebec at Montreal
  
  Canadá
4. [4] Université Paris 7, France
5. [5] Université Paris Est, LIGM, France
Mostrar afiliaciones +
Localización: Journal of pure and applied algebra, ISSN 0022-4049, Vol. 219, Nº 7 (July 2015), 2015, págs. 2521-2537
Idioma: inglés
DOI: 10.1016/j.jpaa.2014.09.014
Enlaces
- Texto completo
Resumen
- We describe in this paper a connection between bifix codes, symbolic dynamical systems and free groups. This is in the spirit of the connection established previously for the symbolic systems corresponding to Sturmian words. We introduce a class of sets of factors of an infinite word with linear factor complexity containing Sturmian sets and regular interval exchange sets, namely the class of tree sets. We prove as a main result that for a uniformly recurrent tree set S, a finite bifix code X on the alphabet A is S-maximal of S-degree d if and only if it is the basis of a subgroup of index d of the free group on A.