The finite index basis property

Valérie Berthé (1) , Clelia de Felice (2) , Francesco Dolce (3) , Julien Leroy (4) , Dominique Perrin (5, 3) , Christophe Reutenauer (6) , Giuseppina Rindone (3)

1 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
2 DIA - Dipartimento Informatica ed Applicazioni "Renato M. Capocelli"
3 LIGM - Laboratoire d'Informatique Gaspard-Monge
4 FNRS - Fonds National de la Recherche Scientifique
5 ESIEE Paris
6 LaCIM - Laboratoire de combinatoire et d'informatique mathématique [Montréal]

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.

Domaines: Informatique [cs]; Mathématiques [math]

Valérie Berthé, Clelia de Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, et al.. The finite index basis property. Journal of Pure and Applied Algebra, 2015, ⟨10.1016/j.jpaa.2014.09.014⟩. ⟨hal-01367681⟩