Séminaires de l'équipe M2F

LaBRI, Bordeaux

Le séminaire M2F a lieu en salle 178 un mardi sur deux à 14H.

Pour proposer un séminaire, le calendrier ci-dessous vous aidera à choisir une date disponible.

Pour s'abonner ou se désabonner de la liste de diffusion.

Pour s'inscrire au calendrier de l'équipe M2F.


Prochains exposés

Tous les exposés sont retransmis en ligne.

Date Exposé de Titre Exposé en présence / virtuel
mardi 5 mars Antoine Amarilli Enumerating Regular Languages in Bounded Delay en présence
We study the task, for a given language L, of enumerating the (generally infinite) sequence of its words, without repetitions, while bounding the delay between two consecutive words. To allow for delay bounds that do not depend on the current word length, we assume a model where we produce each word by editing the preceding word with a small edit script, rather than writing out the word from scratch. In particular, this witnesses that the language is orderable, i.e., we can write its words as an infinite sequence such that the Levenshtein edit distance between any two consecutive words is bounded by a value that depends only on the language. For instance, (a+b)∗ is orderable (with a variant of the Gray code), but a∗+b∗ is not. We characterize which regular languages are enumerable in this sense, and show that this can be decided in PTIME in an input deterministic finite automaton (DFA) for the language. In fact, we show that, given a DFA A, we can compute in PTIME automata A1,…,At such that L(A) is partitioned as L(A1)⊔…⊔L(At) and every L(Ai) is orderable in this sense. Further, we show that the value of t obtained is optimal, i.e., we cannot partition L(A) into less than t orderable languages. In the case where L(A) is orderable (i.e., t=1), we show that the ordering can be produced by a bounded-delay algorithm: specifically, the algorithm runs in a suitable pointer machine model, and produces a sequence of bounded-length edit scripts to visit the words of L(A) without repetitions, with bounded delay -- exponential in |A| -- between each script. In fact, we show that we can achieve this while only allowing the edit operations push and pop at the beginning and end of the word, which implies that the word can in fact be maintained in a double-ended queue.
mardi 19 mars Julie Parreaux TBA TBA
TBA
mardi 9 avril Arnaud Durand TBA en présence
TBA


Calendrier de l'équipe



Archives des années précédentes



Responsables

Igor Walukiewicz, Corto Mascle