Workshop sur la géométrie et la topologie des mots et des langages

Jeudi 21 et Vendred 22 juin à Toulouse

Présentation

The workshop brings together mathematicians and computer scientists on the theme of geometry- topology and languages. The interactions between geometry, topology and languages is old and has its roots already in the late 19th century and early 20th with the pioneering works of Henri Poincare (introduction of the fundamental group) of Max Dehn (geometric approach to the word problem for groups). Since then, the interaction has been a two way street : words and languages can be an algebraic tool for geometry and topology, while the latter is also used to study and estimate the complexity of the former. Recent developments include the theory of rewriting systems, tiling modelings, applied low-dimensional topology, combinatorial word theory.

Programme

Lieux

Institut de Mathématiques de Toulouse, Salle MIP, Bâtiment 1R3. Plus de détails ici.

Titres et abstract des exposés

Guillaume Bonfante: Termination problems in graph rewriting.: The termination of a rewriting system is well covered topic. The main principle is to embed the rewriting relation into a well-founded order. For trees (and terms), many techniques have been proposed. Here we present the case of graphs for which the question is much more open. The technique we introduce relies on the notion of underlying language.
Florian Deloup: Topological Star Height.
Thomas Fernique: From random to quasi-periodic tilings: We shall discuss questions that arise when modeling so-called quasi-crystals by tilings, in particular rhombus tilings of the plane. Those can indeed be easily seen as surfaces in a higher dimensional space. Tilings modeling quasi(crystals obtained by quenching then correspond to maximal entropy random surfaces, while the more recent and nicer annealed quasi(crystals correspond to irrational planes. This rises various theoretical questions (ranging from Markov chain mixing through calculability and combinatorics), most of which are open.
Thierry Monteil: The asymptotic genus of a Wang tile set.: A (Wang) tile set is a finite set of unit squares where each edge got a color. A tile set T tiles the plane if the plane can be covered by Z^2-translated copies of elements of T, where two adjacent edges must have the same color. A tile set is aperiodic if it tiles the plane, but if this can not be done in a periodic way. Most aperiodic tilings are obtained from a substitution process (Penrose, Ammann–Beenker, Robinson,...).
We will introduce the asymptotic genus, a topological invariant that aims at quantifying the level of aperiodicity of a Wang tile set, and discuss its properties. If time permit, we will discuss a metric invariant which allows us to prove that the tile sets of Kari and Culik are not ruled by a substitution.
Svetlana Puzynina: Computing the combinatorial entropy of subshifts.: In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word x contains at least n + 1 distinct factors (i.e., blocks of consecutive symbols) of each length n. They further showed that an infinite word x has exactly n + 1 distinct factors of each length n if and only if x is binary, aperiodic and balanced, i.e., x is a Sturmian word. In this talk I will present a concept of words complexity via group actions and discuss generalizations of the Morse-Hedlund theorem.
Mathieu Sablik: Some problems around subshift of finite type on groups: Un sous shift de type fini sur un groupe G est un coloriage du groupe tel qu'un ensemble fini de motifs ne peut pas aparaître. Il existe une différence profonde suivant que l'on regarde des sous-shift de type fini indexé par Z ou Z². Par exemple il existe des sous-shift de type fini qui ne contient que des configuration apériodique Z² alors que ce n'est pas vrai sur Z. Le but est d'explorer ce genre de question pour d'autres groupes finiment engendré.
Sylvain Salvati: Topology and word combinatorics.: In this talk, I will present a use of Borsuk-Ulam Theorem which solves a discrete problem called the ”splitting necklace problem”. A similar technique allows to prove that the word problem of Zn can be solved by a multiple context-free grammar. Instead of following this proof, we turn to a combinatorial equivalent of Borsuk-Ulam Theorem, Tucker’s Lemma (more precisely the octahedral Tucker lemma). We present a proof that the P`alvo ̈lgyi of the ”splitting necklace problem”. We then show how to adapt this proof so as to show that the word problem in Zⁿ can be solved by a multiple context-free grammar.

Emploi du temps

ICI

Comment arrivé à l'IMT?

IMT's address is the following :
118 Route de Narbonne
31062
Toulouse

The nearest Metro Station is "Université Paul Sabatier" on the yellow metro line (Metro B).

From the Airport : You can :

Take a taxi (the cost depends on the traffic load and on the hour but you should expect to spend between 40 and 65 euros approximately)
Or take the "Navette Tisseo" in front of the arrivals of the airport (it is a bus which leaves every 20 minutes approximately), get down at the stop "Compans Cafarelli" and take the Metro Line B (yellow line) in direction "Ramonville" and stop at "Université Paul Sabatier". The ticket for the "Navette" can be bought at the box office at the exit of the arrivals of the Airport.
Or you can take the Tram line 1 (leaving in front of the arrival of the airport), get down at the terminus ("Palais de Justice") and from there take the metro line 2 (yellow line) in direction "Ramonville" and stop at "Université Paul Sabatier". The ticket of the tram can be bought at the machins in front of the tram.

From the station "Gare Matabiau" :

Take the metro line A (red line) in direction "Basso Cambo" and get down at "Jean Jaurés" (just one stop) then change and take the metro line B (yellow line) in direction "Ramonville" and get down at "Université Paul Sabatier".

Once you are at the metro station "Université Paul Sabatier", you are at approximately 200 m from IMT : the main building of IMT is the building 1R2, in the grid of the campus map it is in the square C4. See the map of the campus here below :

Plan of the Campus

The closest airport is Toulouse Blagnac (TLS), with many flights to european cities and a few intercontinental ones. The centre is conveniently reached with the airport shuttle.
The university can be reached using the Metro B line, stop at "Université Paul Sabatier"; the maths department is in buildings 1R1,1R2,1R3.