We investigate the relation between bifix codes and interval exchange transformations. We prove that the class of natural codings of regular interval echange transformations is closed under maximal bifix decoding.
We investigate the natural codings of linear involutions. We deduce from the geometric representation of linear involutions as Poincare maps of measured foliations a suitable definition of return words which yields that the set of first return words
to a given word is a symmetric basis of the free group on the underlying alphabet $A$. The set of first return words with respect to a subgroup of finite index $G$ of the free group on $A$ is also proved to be a symmetric basis of $G$.
We prove in this note that, for an alphabet with three letters, the set of first return to a given word in a set satisfying the tree condition is a basis of the free group.
We introduce a class of sets of words which is a natural common generalization of Sturmian sets and of interval exchange sets. This class of sets consists of the uniformly recurrent tree sets, where the tree sets are defined by a condition on the pos
sible extensions of bispecial factors. We prove that this class is closed under maximal bifix decoding. The proof uses the fact that the class is also closed under decoding with respect to return words.
Given a set $F$ of words, one associates to each word $w$ in $F$ an undirected graph, called its extension graph, and which describes the possible extensions of $w$ on the left and on the right. We investigate the family of sets of words defined by t
he property of the extension graph of each word in the set to be acyclic or connected or a tree. 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 $F$ is acyclic if and only if any bifix code included in $F$ is a basis of the subgroup that it generates.
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 s
ets of factors of an infinite word with linear factor complexity containing Sturmian sets and regular interval exchange sets, namemly the class of tree sets. We prove as a main result that for a uniformly recurrent tree set $F$, a finite bifix code $X$ on the alphabet $A$ is $F$-maximal of $F$-degree $d$ if and only if it is the basis of a subgroup of index $d$ of the free group on $A$.
We introduce a definition of admissibility for subintervals in interval exchange transformations. Using this notion, we prove a property of the natural codings of interval exchange transformations, namely that any derived set of a regular interval ex
change set is a regular interval exchange set with the same number of intervals. Derivation is taken here with respect to return words. We characterize the admissible intervals using a branching version of the Rauzy induction. We also study the case of regular interval exchange transformations defined over a quadratic field and show that the set of factors of such a transformation is primitive morphic. The proof uses an extension of a result of Boshernitzan and Carroll.
We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids ge
nerated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.
