Orateurs invités

Raluca Uricaru (Bordeaux) Graphs for Genomic Sequences

présentation

In this presentation, after an introduction to bioinformatics and to the latest challenges in the field, I will focus on problems concerning data (genomic sequences in a four letter alphabet, i.e., A, T, G, C) generated by Next Generation Sequencing technologies. More specifically, I will dwell on the modélisation of problems like the problem of assembly of genomes and on solutions based on graphs (like overlap graphs and De Bruijn graphs).

Laure Daviaud (Warwick) About the generalised star-height problem

présentation

In this talk, I will discuss about the generalised star-height problem: given a rational language L and an integer k, is L characterised by a rational expression using union, concatenation, complement and at most k nested stars?  For k=0, this problem is known to be decidable, and the languages satisfying this condition form the well-known class of star-free languages.  I will explain how this decidability result works, describing the notion of identities for rational languages.

Pascal Hubert (Marseille) Rigidity of square-tiled interval exchange transformations and translation flows

In this talk, we will discuss a joint work with Sébastien Ferenczi about rigidity of a class of interval exchange transformations (iet). Veech proved that almost every interval exchange transformation is rigid. It is difficult to provide examples of non rigid iets. Square-tiled surfaces form a very natural class of translation surfaces those whose periods belong to the integer lattice. We will give a necessary and sufficient condition to get rigidity of a linear flow on such a surface and of the associated iet.

Émilie Charlier (Liège)Nyldon words

présentation

The theorem of Chen-Fox-Lyndon states that every finite word w over a fixed alphabet A$ can be uniquely factorized as w=l1··· lk, where (l1, ..., lk) is a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to define the family of Lyndon words over A in a recursive way:

1. the letters are Lyndon;
2. a finite word of length greater than one is Lyndon if it cannot be factorized into a nonincreasing sequence of shorter Lyndon words.

In a post on Mathoverflow in November 2014, Darij Grinberg defines a variant of Lyndon words, which he calls Nyldon words, by reversing the lexicographic order in the previous recursive definition. The class of words so obtained is not, as one might first think, the class of maximal words in their conjugacy classes. Gringberg asks three questions:

1.  How many Nyldon words of length n are there?
2. Is there an equivalent to the Chen-Fox-Lyndon theorem for Nyldon words?
3. Is it true that every primitive words admits exactly one Nyldon word in his conjugacy class?

In this talk, I will discuss these questions in the more general context of Lazard factorizations of the free monoid and show that each of Grinberg's questions has a positive answer. This is a joint work with Manon Philibert (ENS Lyon) and Manon Stipulanti (ULiège).

Philippe Schnoebelen (LSV, CNRS, ENS Paris-Saclay)  Simple algorithms and fast-growing complexity for well-structured systems

présentation

Well-quasi-orderings (WQOs) are a fundamental tool in logic and computer science. They are the basis of a large number of finiteness/regularity/termination/... results. In constraint solving, automated deduction, program analysis, and many more fields, wqos usually appear under the guise of specific tools, like Dickson's Lemma (for tuples of integers), Higman's Lemma (for words and their subwords), Kruskal's Tree Theorem and its variants (for finite trees with embeddings), and recently the Robertson Seymour Theorem (for graphs and their minors). What is not very well known is how to analyze the complexity of wqo-based algorithms.

In this talk we survey two lines of recent developments in well-structured systems: (1) generic algorithms and data structures for computing with upward-closed and downward-closed sets in wqos, and (2) generic tools for demonstrating complexity bounds in wqo-based algorithms and systems.