Posts classified under: Séminaire Algo

En informatique théorique, la combinatoire des mots consiste à étudier des séquences de symboles appelées des mots sur un alphabet. Ce concept est bien adapté à la description de la succession d’événements à l’intérieur d’une séquence musicale. Nous l’avons utilisé pour étudier certains rythmes dans les musiques africaines de la forme 3 2n 3 2 n+1 (pour n = 0 … Continue reading Séminaire Algorithmique : « Combinatoire de mots, musiques traditionnelles et improvisation avec ordinateur », Marc Chemillier (EHESS, Paris)

Une configuration est un coloriage du plan Z². Habituellement, les ensembles de configurations étudiés sont ceux définis par un ensemble de motifs “interdits” n’apparaissant dans aucune des configurations de l’ensemble. De tels ensembles sont appelés sous-shifts. Dans ce séminaire, on définit les ensembles de configurations grâce à la logique Monadique du Second Ordre (MSO), et … Continue reading Séminaire Algorithmique : « Classes de sous-shifts définis par des formules logiques », Rémi Pallen (ENS Paris Saclay)

Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n to 2^n. In this talk, we investigate this classical result in a probabilistic setting where we take a random … Continue reading Séminaire Algorithmique : « Random Deterministic Automata With One Added Transition », Cyril Nicaud (LIGM, Univ. Paris-Est)