Project topics and materials
Get Complete Project Material File(s) Now! »
Free groups and laminary sets
We fix our notation concerning free groups (see, for example, [53]). Given an alphabet A be an alphabet we denote by A−1 = {a−1 | a ∈ A} a new alphabet called the inverse of A. Given a word w = a0a1 · · · an−1 its inverse is the word w−1 = a−1 n−1a−1 n−2 · · · a−1 0 .
We denote by FA the free group on the alphabet A. It is identified with the set of all words on the alphabet A ∪ A−1 which are reduced, in the sense that they do not have any factor aa−1 or a−1a for a ∈ A. Sometimes we also denote by ¯a the inverse a−1 of a letter a ∈ A.
Note that when u is a prefix of v, we recover the definition of u−1v given at the end of the previous subsection. We extend the bijection a 7→ a−1 to an involution on A ∪ A−1 by defining (a−1)−1 = a. For any word w on A ∪ A−1 there is a unique reduced word equivalent to w modulo the relations aa−1 ≡ a−1a ≡ ε for a ∈ A. If u is the reduced word equivalent to w, we say that w reduces to u and we denote w ≡ u. We also denote u = ρ(w). The product of two elements u, v ∈ FA is the reduced word w equivalent to uv, namely ρ(uv). A set of reduced words on the alphabet A ∪ A−1 is said to be symmetric if it contains the inverses of its elements. A symmetric factorial set of reduced words on the alphabet A ∪ A−1 is called a laminary set on A. An infinite laminary set S is called semi-recurrent if for any u,w ∈ S, there is a v ∈ S such that uvw ∈ S or uvw−1 ∈ S. Likewise, it is said to be uniformly semi-recurrent if for any word u ∈ S there is an integer n ≥ 1 such that for any word w of length n in S, u or u−1 is a factor of w. A uniformly semi-recurrent set is semi-recurrent.
Acyclic, connected and tree sets
Let S be a biextendable set. We say that S satisfies the acyclicity condition, or simply that S is acyclic if for every word w ∈ S, the graph ES(w) is acyclic. A set S satisfies the connection condition, or simply S is connected, if for every word w ∈ S, the graph ES(w) is connected.
Generalized extension graphs
In this section we consider a variant of the extension graph.
Let S be a set. For w ∈ S, and U, V ⊂ S, let US(w) = {ℓ ∈ U | ℓw ∈ S} and let VS(w) = {r ∈ V | wr ∈ S}. The generalized extension graph of w relative to U, V is the following undirected graph EU,V S (w). The set of vertices is made of two disjoint copies of US(w) and VS(w). The edges are the pairs (ℓ, r) for ℓ ∈ US(w) and r ∈ VS(w) such that ℓwr ∈ S. The extension graph ES(w) defined previously corresponds to the case where U, V = A.
Table of contents :
R´esum´e de la th`ese
Introduction
1 Preliminaries
1.1 Words and sets
1.1.1 Free groups and laminary sets
1.1.2 Morphisms
1.1.3 Extension graphs
1.2 Bifix codes
1.2.1 Parses and degree
1.2.2 Derived codes and coding morphisms
1.2.3 Internal transformations
1.2.4 Composition of codes
1.3 Automata
1.3.1 Groups and automata
1.3.2 Rauzy graphs
1.4 Return words
1.4.1 Derived sets
2 Neutral sets
2.1 Strong, weak and neutral sets
2.1.1 Probability distributions
2.2 Cardinality Theorems
2.2.1 Bifix codes
2.2.2 Return words
2.3 Bifix decoding of neutral sets
3 Tree sets
3.1 The tree condition
3.1.1 Acyclic, connected and tree sets
3.1.2 Planar trees
3.1.3 Generalized extension graphs
3.2 Return words in tree sets
3.2.1 Rauzy graphs
3.2.2 The Return Theorem
3.2.3 Derived sets of tree sets
3.3 Multiplying maps
3.4 Palindromes
4 Bifix codes in tree sets
4.1 Bifix codes in acyclic sets
4.1.1 Incidence graph
4.1.2 Coset automaton
4.1.3 Freeness Theorems
4.1.4 Saturation Theorem
4.2 Finite index basis property
4.2.1 The Finite Index Basis Theorem
4.2.2 Tame bases
4.2.3 S-adic representations
4.3 Bifix decoding of tree sets
4.3.1 Maximal bifix decoding
4.3.2 Composition of bifix codes
4.3.3 Modular codes
5 Specular sets
5.1 Specular groups
5.1.1 Subgroups
5.1.2 Monoidal basis
5.2 Specular sets
5.2.1 Odd and even words
5.2.2 Bifix codes in specular sets
5.2.3 Doubling maps
5.2.4 G-Palindromes
5.3 Return words
5.3.1 Cardinality Theorems for return words
5.3.2 First Return Theorem for specular sets
5.4 Freeness and Saturation Theorems
5.4.1 Freeness Theorem
5.4.2 Cosets
5.4.3 Saturation Theorem
5.5 The Finite Index Basis property
5.5.1 Finite Index Basis Theorem
5.5.2 A converse of the Finite Index Basis Theorem
6 Interval exchanges
6.1 Interval exchange transformations
6.1.1 Regular interval exchanges
6.1.2 Natural coding
6.1.3 Interval exchange sets
6.1.4 Planar tree sets
6.2 Bifix codes and interval exchanges
6.2.1 Prefix and bifix codes
6.2.2 Maximal bifix codes
6.2.3 Maximal bifix decoding
6.2.4 Subgroups of finite index
7 Branching Rauzy induction
7.1 Induced transformations and admissible intervals
7.1.1 Induced transformations
7.1.2 Admissible semi-intervals
7.1.3 Derived sets
7.2 Rauzy induction
7.2.1 One-side Rauzy induction
7.2.2 Branching induction
7.2.3 Equivalence relation
7.2.4 Induction and automorphisms
7.3 Interval exchanges over a quadratic field
7.3.1 Complexities
7.3.2 Return times
7.3.3 Reduced complexity of admissible semi-intervals
7.3.4 Primitive morphic sets
8 Linear involutions
8.1 Linear involution
8.1.1 Generalized permutations and linear involutions
8.1.2 Linear involutions and interval exchanges
8.1.3 Coherent and orientable linear involutions
8.1.4 Minimal involutions
8.2 Natural coding
8.2.1 Infinite natural coding
8.2.2 Orientability and uniform recurrence
8.2.3 Linear involutions and specular sets
8.2.4 Mixed return words
8.2.5 Admissible intervals
Conclusions
Bibliography
