![[.ics]](small_ics.png)
| Orateur | Laura Ciobanu (University of Neuchâtel, ) |
| Date | Mardi 12 janvier 2016 |
| Salle | salle 76 |
| Titre | The language complexity of solutions of equations in free semigroups and free groups |
| Résumé | We show that, given a word equation over a finitely generated free group (or semigroup), the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. This is joint work with Murray Elder and Volker Diekert. |
| Orateur | Nathanaël Fijalkow (Oxford University, ) |
| Date | Mardi 8 décembre 2015 |
| Salle | salle 76 |
| Titre | Online Space Complexity |
| Résumé | In this talk, I will speak about the Online Space Complexity of languages, which is an old topic (studied by Karp, Minsky, Hartmanis and others in the 60s) that I picked up recently. The main question is the following: given a language L, how many states does an automaton need to recognise L, as a function of the input length? This question is well-understood for regular languages, which are those recognised by finite automata, so we go beyond this case and study non-regular languages. This talk will be a gentle introduction to these questions; I will present some results about the online space complexity of probabilistic languages. |
| Orateur | Félix Baschenis (LaBRI, ) |
| Date | Mardi 24 novembre 2015 |
| Salle | salle 178 |
| Titre | From two-way to one-way word transducers |
| Résumé | While adding to automata the possibility of their reading head to move freely from left to right and right to left does not change their expressive power, this is not the case for transducers. In this talk, we will present several models of transducers that are strictly more expressive than one way transducers, and study how to decide when a transduction defined by one of those models is definable by a one-way transducer. In particular we will see how we can improve the complexity of the decision procedure by restricting our model so that changes of the direction of the lecture head can only appear at the borders of the input tape. We will also present how different transduction models are related, and how the number of reversals of the lecture head is linked to the number of variables of some streaming string transducers. This may yields to a procedure for minimizing this number of variables, which is a difficult open problem. |
| Orateur | Bruno Courcelle (LaBRI, ) |
| Date | Mardi 10 novembre 2015 |
| Salle | salle 178 |
| Titre | Régularité et définissabilité en logique du second ordre monadique des quasi-arbres (suite) |
| Résumé | Un quasi-arbre est un arbre dénombrable tel que le "chemin" entre 2 noeuds peut être infini. Les quasi-arbres sont engendrés par un nombre fini d'opérations via des termes infinis. Les quasi arbres réguliers sont ceux définis par des termes réguliers. Ce sont exactement ceux définissables en logique du second ordre monadique. Ce résultat utilise et généralise un résultat de W. Thomas (1986) sur les mots infinis généralisés, les "arrangements" que j'ai étudiés en 1978. Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any finite or countable order type, in particular that of rational numbers. They are used to define the rank-width of a countable graph in such a way that it is the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed "trees" and they are also useful to define the modular decomposition of a countable graph. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones definable by (i.e., are the unique models of) monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders. |
| Orateur | Bruno Courcelle (LaBRI, ) |
| Date | Mardi 13 octobre 2015 |
| Salle | salle 178 |
| Titre | Régularité et définissabilité en logique du second ordre monadique des quasi-arbres |
| Résumé | Un quasi-arbre est un arbre dénombrable tel que le "chemin" entre 2 noeuds peut être infini. Les quasi-arbres sont engendrés par un nombre fini d'opérations via des termes infinis. Les quasi arbres réguliers sont ceux définis par des termes réguliers. Ce sont exactement ceux définissables en logique du second ordre monadique. Ce résultat utilise et généralise un résultat de W. Thomas (1986) sur les mots infinis généralisés, les "arrangements" que j'ai étudiés en 1978. Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any finite or countable order type, in particular that of rational numbers. They are used to define the rank-width of a countable graph in such a way that it is the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed "trees" and they are also useful to define the modular decomposition of a countable graph. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones definable by (i.e., are the unique models of) monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders. |
| Orateur | Sylvain Lombardy (LaBRI, ) |
| Date | Mardi 6 octobre 2015 |
| Salle | salle 75 |
| Titre | Two-way weighted automata and representations. |
| Résumé | Two-way automata were defined in the early years of automata theory. They are as powerful as one-way automata but they can recognize some languages with fewer states. Weighted automata realize functions (or series): they assign a value to each of their inputs. Two-way weighted automata are strictly more powerful than one-way ones. In this talk, we try to describe the series realized by two-way weighted automata, we extend the notion of linear representations that is the foundation of the algebraic study of rational series, and we study the fixed-point equation fulfilled by series realized by two-way weighted automata. |
| Orateur | Szymon Toruńczyk (University of Warsaw, ) |
| Date | Mardi 22 septembre 2015 |
| Salle | salle 76 |
| Titre | A profinite approach to limitedness |
| Résumé | The theory of regular cost functions developed Thomas Colcombet is a generalization of the theory of regular languages which can encompass boundedness phenomena. I will give a profinite approach to this theory. In particular, I will recall the notion of profinite words, and present the B-variants of finite automata, regular expressions, and semigroups, which can accept profinite words, and discuss how they relate to the limitedness problem and the theory of Colcombet. |
| Orateur | Santiago Figueira (University of Buenos Aires, ) |
| Date | Mardi 15 septembre 2015 |
| Salle | salle 76 |
| Titre | A short tutorial on algorithmic randomness |
| Résumé | When would you say that an infinite binary sequence is ‘random’? The first answer that comes to our mind is probably that such sequence is random if it looks like the output of a coin tossing. That is not a formal definition. How to transform our intuition of ‘randomness’ into a meaningful mathematical definition is not an easy task. This talk will be a non-technical tutorial: I will present the main definitions of ‘algorithmic randomness’, which are inspired in very different paradigms, each of it capturing some aspect of our intuition behind this concept. I will also highlight the main connections to computability theory. |