Fiche du document
2015
- handle: 10670/1.newexp
- Berthé, Valérie; De Felice, Clelia; Dolce, Francesco; Leroy, Julien; Perrin, Dominique; Reutenauer, Christophe et Rindone, Giuseppina (2015). « Acyclic, connected and tree sets ». Monatshefte für Mathematik, 176(4), pp. 521-550.
Ce document est lié à :
http://archipel.uqam.ca/8349/
Ce document est lié à :
http://dx.doi.org/10.1007/s00605-014-0721-4
Ce document est lié à :
doi:10.1007/s00605-014-0721-4
Sujets proches
Family Family structure Families--Social aspects Families--Social conditions Family life Structure, Family Family relationships Relationships, Family Combinatorics Biography--Ancestry Relations with family Biography--Descendants Biography--Family AncestryCiter ce document
Valérie Berthé et al., « Acyclic, connected and tree sets », UQAM Archipel : articles scientifiques, ID : 10670/1.newexp
Métriques
Partage / Export
Résumé
Given a set S of words, one associates to each word w in S an undirected graph, called its extension graph, and which describes the possible extensions of w in S on the left and on the right. We investigate the family of sets of words defined by the property of the extension graph of each word in the set to be acyclic or connected or a tree. We exhibit for this family various connexions between word combinatorics, bifix codes, group automata and free groups. We prove that in a uniformly recurrent tree set, the sets of first return words are bases of the free group on the alphabet. Concerning acyclic sets, we prove as a main result that a set S is acyclic if and only if any bifix code included in S is a basis of the subgroup that it generates.