À propos de moi

Je viens de terminer mon doctorat sous les directions cotutellesques de Christian Choffrut et Giovanni Pighizzini, respectivement à l’IRIF (anciennement LIAFA), Université Paris-Diderot, Paris 7 et au Dipartimento di Informatica, Università degli studi di Milano. Je vais prochainement démarrer un post-doctorat à Varsovie avec Mikołaj Bojańczyk.

Mon CV est disponible en français et en anglais .

J’ai soutenu ma thèse le 30 mai dernier. Voici le mémoire , les remerciements et voici mes planches pour la présentation .

Contact

En ce moment je suis à Paris.

mail: prenom ˳ nom Ə liafa ˳ univ-paris-diderot ˳ fr
bâtiment Sophie Germain 8 place Aurélie Nemours — F-75013 Paris, 4ème étage, bureau 4059 (voyez)
Via Comelico 39 — 20135 Milano, Terzo Piano, stanza T310

Événements

Prochainement

DLT 2016, 25 au 28 juillet 2016, Montréal — Résumé

Both ways rational functions

Bruno Guillon (IRIF, Université Paris Diderot − Paris 7, DI, Università degli studi di Milano) Christian Choffrut (IRIF, Université Paris Diderot − Paris 7)

We consider binary relations on words which can be recognized by finite two-tape devices in two different ways: the traditional way where the two tapes are scanned in the same direction and a new one where they are scanned in different directions. The devices of the former type define the family of rational relations, while those of the latter define an a priori really different family. We characterize the partial functions that are in the intersection of the two families. We state a conjecture for the intersection for general, nonfunctional, relations.

Ma soutenance de thèse, 30 mai 2016, Paris — manuscript , remerciements et slides

Précédemment

École Jeunes Chercheurs en Informatique Mathématique, 4-8 avril, Strasbourg −
GT ALGA − Annual Meeting 2016, 11 & 12 avril, LIF, Marseille
Colloque en l’honneur de Marcel-Paul Schützenberger au LaBRI, 21-25 mars, Bordeaux −
Séminaire Automate à l’Irif, 12 février 2016, Paris − Résumé

On two-way transducers

Bruno Guillon (IRIF, Université Paris Diderot − Paris 7, DI, Università degli studi di Milano)

A transducer is a finite automaton equipped with an output tape, scanned in one direction by a write-only output head. At each step of the computation, a word associated with the chosen transition is appended on to the output tape. Such a device accepts a relation on words, i.e., a subset of Σ^* × Γ^* where Σ (resp. Γ) is the input (resp. output) alphabet. The model admits different variants, namely one-way deterministic (1DT), one-way nondeterministic (1NT), two-way deterministic (2DT), and two-way nondeterministic (2NT). Contrary to the case of finite automaton, each version accepts a distinct family of relations. Until now and despite the simplicity of the model, no characterization of the most general variant, namely the 2NT, has been established.

I will introduce all these devices, and additional operations on relations. Then I will give an algebraic characterization of the relations accepted by 2NT, in the particular case of unary input and output alphabets, that is, when both Σ and Γ are reduced to a single letter. Then I will show with some provable examples that these strong assumptions are required. Finally, I will give some general remarks and corollaries.

MFCS 2015, Milan
NCMA 2015, Porto —
Journée MDSC, 11 juin 2015, Nice-Sophia-Antipolis: Résumé

Caractérisation algébrique des relations acceptées par transducteurs bidirectionnels unaires

Bruno Guillon (LIAFA, Université Paris Diderot − Paris 7, DI, Università degli studi di Milano)

Les transducteurs sont des extensions d’automates finis qui sont capable d’écrire des mots sur un ruban de sortie en écriture seule durant leur calcul. Ils reconnaissent donc des relations sur les mots. Les transducteurs unidirectionnels unaires acceptent exactement la classe des relations rationnelles. Cependant, les transducteurs bidirectionnels étendent strictement la puissance calculatoire des transducteurs unidirectionnel, même dans le cas d’alphabets (d’entrée et de sortie) unaires (c’est à dire ne contenant qu’une seule lettre).

Après avoir introduit le modèle par des exemples simples, je présenterai les grandes lignes d’une construction, basée sur les crossing sequences, qui permet d’obtenir une caractérisation des relations acceptées par des transducteurs bidirectionnels dans le cas particulier d’alphabets d’entrée et de sortie unaires. Je discuterai ensuite des extensions et des conséquences de ce résultat.

Collaboration avec Christian Choffrut.

Jadis

Exposés précédents

ÉJCIM, Orléans, 2 Avril 2015 —
ICTCS, Pérouse, 17 Septembre 2015 —
MFCS, Budapest, 15 Août 2015 —
Séminaire au DI, Milan, 2 Juillet 2014 —
Séminaire Thésards (LIAFA & PPS), Paris, 22 Janvier 2014
Séminaire à Rouen, 28 Novembre 2013 —
Journée de rentrée de l’équipe Automate (LIAFA), Paris, 11 Octobre 2013 —
Journée des entrants (LIAFA), Paris, 10 Octobre 2012 —
ÉJCIM, Rennes, 19 Mars 2012 —

Recherche

Je m’intéresse principalement aux extensions d’automates finis bidirectionnels. Je joue sur cette capacité à déplacer la tête de lecture en avant et en arrière, mais aussi sur le non-déterminisme, le nombre de ruban, le nombre de tête de lecture, la présence d’une pile ou d’un compteur, la taille de l’alphabet. Ma recherche est principalement orienté dans deux directions:

d’un côté je cherche à déterminer la puissance calculatoire de certains modèles non classiques. +
Ceci passe par des caractérisations, ou des résultats d’équivalence entre différents modèles. En particulier, je m’intéresse aux transducteurs (voire, plus généralement, aux automates pondérés) non-déterministes bidirectionnels, en essayant de caractériser algébriquement leur puissance calculatoire. J’ai étudié trois opérations algébriques dans le but de décrire la dynamique d’une telle machine:
- le produit d’Hadamard (la concaténation de deux images associées par deux relations à une même entrée), qui décrit la possibilité de lire (de gauche à droite) plusieurs fois une entrée,
- l’étoile d’Hadamard (la concaténation d’un nombre arbitraire d’images associées à une même entrée, par une relation), qui étend la possibilité précédente à un nombre arbitraire de fois,
- le miroir (l’image associée au miroir (renversé) d’une entrée), qui décrit donc la possibilité de lire l’entrée de droite à gauche.
La famille des relations Hadamard (Had) est alors la clôture par union, produit d’Hadamard et étoile d’Hadamard de la famille des relations rationnelles (Rat), qu’elle étend strictement, même dans le cas où les deux alphabets (entrée et sortie) sont unaires. L’ajout de l’opération miroir conduit à la définition d’une super-famille : les relations Miroir-Hadamard (MHad). On peut alors comparer les deux familles avec les ensembles de relations acceptées par des transducteurs à la bidirectionalité restreinte (eg, boustrophédon, rotatif), ce qui donne la jolie figure ci-dessous.

d’un autre côté, je m’interesse à la complexité descriptionnelle, en comparant le taille (souvent le nombre d’états) de différents modèles reconnaissant le même ensemble (langage, relation, fonction, etc.).

Publications

Jetez un coup d’œil à ma page dblp .

Journal

Viliam Geffert Bruno Guillon Giovanni Pighizzini
Two-way automata making choices only at the endmarkers

The question of the state-size cost for simulation of two-way nondeterministic automata (2nfas) by two-way deterministic automata (2dfas) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2dfas (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2nfas. Here we use an opposite approach, increasing the power of 2dfas to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2dfas. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2nfas and 2dfas can be obtained only for unrestricted 2nfas using capabilities beyond the proposed new model.

As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2dfas would imply L≠NLL≠NL. In the same way, the alternating version of these machines is related to L ≟ NL ≟ P, the classical computational complexity problems.

10.1016/j.ic.2014.08.009

Inf. Comput. 239 71–86 2014

Conférence

Christian Choffrut Bruno Guillon
Both ways rational relations

We consider binary relations on words which can be recognized by finite two-tape devices in two different ways: the traditional way where the two tapes are scanned in the same direction and a new one where they are scanned in different directions. The devices of the former type define the family of rational relations, while those of the latter define an a priori really different family. We characterize the partial functions that are in the intersection of the two families. We state a conjecture for the intersection for general, nonfunctional, relations.

10.1007/978-3-662-53132-7_10

DLT 16 114-124
Bruno Guillon
Sweeping weakens two-way transducers even with a unary output alphabet.

In a previous paper we showed that the two-way transducers with unary input and output alphabets have the same recognition power as the non-sweeping ones. We show that this no longer holds when the output alphabet is still unary but the input alphabet is arbitrary.

NCMA 2015 91-108
Christian Choffrut Bruno Guillon
An algebraic characterization of unary two-way transducers

Two-way transducers are ordinary finite two-way automata that are provided with a one-way write-only tape. They perform a word to word transformation. Unlike one-way transducers, no characterization of these objects as such exists so far except for the deterministic case. We study the other particular case where the input and output alphabets are both unary but when the transducer is not necessarily deterministic. This yields a family which extends properly the rational relations in a very natural manner. We show that deterministic two-way unary transducers are no more powerful than one-way transducers.

ICTCS 2014 279-283
Christian Choffrut Bruno Guillon
An Algebraic Characterization of Unary Two-Way Transducers

Two-way transducers are ordinary finite two-way automata that are provided with a one-way write-only tape. They perform a word to word transformation. Unlike one-way transducers, no characterization of these objects as such exists so far except for the deterministic case. We study the other particular case where the input and output alphabets are both unary but when the transducer is not necessarily deterministic. This yields a family which extends properly the rational relations in a very natural manner. We show that deterministic two-way unary transducers are no more powerful than one-way transducers.

10.1007/978-3-662-44522-8_17

MFCS 2014 196–207
Viliam Geffert Bruno Guillon Giovanni Pighizzini
Two-way Automata Making Choices Only at the Endmarkers

The question of the state-size cost for simulation of two-way nondeterministic automata (2nfas) by two-way deterministic automata (2dfas) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2dfas (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2nfas. Here we use an opposite approach, increasing the power of 2dfas to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2dfas. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2nfas and 2dfas can be obtained only for unrestricted 2nfas using capabilities beyond the proposed new model.

As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2dfas would imply L ≠ NL. In the same way, the alternating version of these machines is related to L ≟ NL ≟ P, the classical computational complexity problems.

10.1007/978-3-642-28332-1_23

LATA 2012 264–276

Soumis

Bruno Guillon
Input- or output-unary sweeping transducers are weaker than their 2-way counterparts

In a previous paper we showed that two-way (nondeterministic) transducers with unary input and output alphabets have the same recognition power as the sweeping ones. We show that this no longer holds when one of the alphabets has cardinality at least 2.

Dans un article précédent, nous avons montré que les transducteurs non-déterministes bidirectionnels sur des alphabets d’entrée et de sortie unaires, ont la même puissance de reconnaissance que les transducteurs boustrophédons. Nous prouvons ici que ce résultat n’est plus vrai, lorsque l’un des alphabet est de cardinalité au moins 2.

RAIRO-ITA

Autres écrits

Preprints

Viliam Geffert Bruno Guillon Giovanni Pighizzini
Two-Way Automata Making Choices Only at the Endmarkers

The question of the state-size cost for simulation of two-way nondeterministic automata (2NFAs) by two-way deterministic automata (2DFAs) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2DFAs (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2NFAs. Here we use an opposite approach, increasing the power of 2DFAs to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2DFAs. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2NFAs and 2DFAs can be obtained only for unrestricted 2NFAs using capabilities beyond the proposed new model. As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2DFAs would imply L<>NL. In the same way, the alternating version of these machines is related to L =? NL =? P, the classical computational complexity problems.

arXiv.org 2011 —

Stages

Communicating Finite Automata System and Tally Languages 2012, Master 2

rapport (en anglais) et soutenance (en français) .
2-ways outer-nondeterministic finite automata and descriptional complexity 2011, Master 1

rapport (en anglais) et soutenance (en français) .

Enseignements

Depuis 2012 j’enseigne en Licence d’Informatique (travaux dirigés, travaux pratiques) à l’Université Paris Diderot (Paris 7).

M1XML — comme XML en Master 1 (2015)
La page des travaux dirigés offre une panoplie d’exercices pédagogiques, en difficulté croissante.

On commence doucement en parlant de la structure générale d’un document xml, qu’on peut ensuite restreindre par des dtd et des schéma xsd. Puis on débouche sur de l’analyse avec des schématrons et surtout xslt, et ça se complique.
AL5 — comme Algorithmique 5^ème semestre (2015)
On voit et revoit bon nombre d’algorithmes connus (Parcourt d’arbre, en l’argeur, en profondeur, parcourt de Graphe, Algorithme de Kruskal, Tarjan, Prim, Dijkstra…). On étudie leur complexité, leurs applications, leur correction. On revoit aussi quelques structures de données (tas, tas de Fibonacci…).
PI4 — comme Projet Informatique 4^ème semestre (2016)
Il s’agit d’encadrer des étudiants travaillant par groupe de 3/4 sur un projet pendant tout le semestre. J’ai proposé deux sujets qui viennent s’ajouter aux sujets proposés par les autres encadrants : SeamCarving (présentation ) et Labyrinthe (présentation ).
CI2 — comme Concept Informatique 2^ème semestre (2015)
Dans ce cours on étudie ce qu’il se passe dans l’ordinateur lors de l’exécution d’un programme.

En attendant d’en dire plus, voici la correction de l’exercice 1 du TD9 sur le Backtracking (non fait) pour les vacanciers courageux. Il s’agit de trouver tous les carré latins normalisés de dimension quelconque.
IO2 — comme Internet & Outils 2^ème semestre (2015)
IF1 — presque comme Introduction à l’informatique et à la programmation 1^er semestre (2013)
IK3 — pas du tout comme Projets informatiques 3^ème semestre en équipe et en java (2011 et 2013)

Liens

Amitiés informatiques

Crowd Event sera bientôt une application qui met en lien des artistes, des scènes (des bars) et un public.
Jeanne Guillon et Aurélien Delsaux font entre-autre du Théâtre d’Art pour Tous : l’Arbre.
Catherine Prady fait de la traduction french2english.
La cyclofficine d’Ivry, un lieu bien sympathique pour y réparer son vélo,

Outils

Firefox est un navigateur libre qui jouit d’une multitude d’extensions.:
- Vimperator (qu’on peut booster aver Pterosaur) pour avoir un fonctionnement à la vim (fonctionnement que l’on peut retrouver dans le navigateur minimal Vimb),
- uBlock, pour bloquer les publicités,
- tree Style Tab, pour afficher ses onglets sous forme d’arbre,
- Markdown Here, pour compiler un texte en Markdown (notamment dans les mails),
- Markdown Viewer, pour visualiser des fichiers Markdown,
- DuckDuckGo et ses !, pour effectuer des recherches privées rapidement.
Je signale quelques outils en ligne.:
- OpenStreetMap,
- OpenRouteService, pour trouver un bon itinéraire, y compris à vélo,
- Météo dans l’heure, pour savoir quand faire ses petits trajets en vélo,
- Wikipedia, bien sûr,
- Trello, pour organiser une collaboration,
- Qwant, pour rechercher de façon privée,
- Capitaine Train, pour voyager en train et en bus en Europe (mais surtout en France).
En tant qu’utilisateur de Linux convaincu, je souligne quelques programmes et astuces.:
- meld, permet de comparer des fichiers ou des repertoires,
- rsync, permet de synchroniser des répertoires y compris distant,
- CDPATH, est une variable d’environnement qui facilite grandement ma navigation locale en ligne de commande,
- mercurial et git, gère mes versions de projets.

Culture et Science

Sans être un grand fan de la Physique, j’ai bien aimé la vidéo du cours ‘Introduction à la Relativité restreinte’, de Richard Taillet. C’est enrichissant scientifiquement et pédagogiquement. Les cours sont disponibles ici.

Finite Automata

Bruno Guillon