About me
I am now a postdoc in the department of computer science of University of Milan, working with Giovanni Pighizzini and Luca Prigioniero.
From September 2016 to April 2017, I was a postdoc in University of Warsaw at the Faculty of Mathematics, Informatics and Mechanics under supervision of Mikołaj Bojańczyk, as part of the project «A unified theory of finitestate recognisability» (ERC project LIPA).
Before that, I was a PhD student in IRIF − Université Paris Diderot, PARIS VII and in DI − Università degli studi di Milano.
My Curriculum Vitæ is available here (last update: 04/2017).
Contact
Events
Shorty
 International training school on reversible computation, August 28–31 2017, Toruń – ICT COST Action IC1405
 Highlights of Logic, Games and Automata, September 12–15 2017, London
Previously
 ICALP 2017, July 10–14 2017, Warsaw —
Which classes of origin graphs are generated by transducers?
We study various models of transducers equipped with origin information. We consider the semantics of these models as particular graphs, called origin graphs, and we characterise the families of such graphs recognised by streaming string transducers.
This work has been published in proceedings of ICALP 2017. Preprint (long version): . Slides: .
 Lipa summer school, July 3–6 2017, Warsaw
 Journées ALGA & Vérif, May 29–31 2017, Créteil —
Which classes of origin graphs are generated by transducers?
This talk is about transductions, which are binary relations on words. We are interested in various models computing transductions (ie, transducers), namely twoway automata with outputs, streaming string transducers and stringtostring MSO transductions. We observe that each of these formalisms provides more than just a set of pairs of words. Indeed, one can also reconstruct origin information, which says how positions of the output string originate from positions of the input string. On the other hand, it is also possible to provide any pair of words in a relation with an origin mapping, indicating an origin input position for each output position, in a similar way. This defines a general object called origin graph. We characterise the families of origin graphs which corresponds to the semantics of some classical models of transducer. We also prove the decidability of the MSO satisfiability problem on the classes of origin graphs generated by streaming string transducers or equivalently by stringtostring MSO transductions.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle.
This work has been accepted at ICALP 2017. Preprint (long version): .
 Dagstuhl seminar, April 02–05 2017, Leibniz —
Which classes of origin graphs are generated by transducers?
We consider the origin semantics of transducers (2way automata with outputs, streaming string transducers, stringtostring MSOtransduction) which extends relations by providing a mapping from positions of the output into positions of the input, saying how the output originates from the input. In the other hand, every relation on words can be extended by such a mapping, leading to the notion of origin transduction, viewed as set of particular graph, namely the origin graphs. We exhibit structural properties of origin transductions which are necessary and sufficient for characterising the origin semantics of streaming string transducers.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle.
This work has been accepted in ICALP 2017. Preprint (long version): .
 Seminar Automata at MIMUW, February 15th 2017, Warszawa —
Regular transductions with origin semantics
This talk is about transductions, which are binary relations on words. We are interested in various models computing transductions (ie, transducers), namely twoway automata with outputs, streaming string transducers and stringtostring MSO transductions. We observe that each of these formalisms provides more than just a set of pairs of words. Indeed, one can also reconstruct origin information, which says how positions of the output word originate from positions of the input word. It is also possible to provide any pair of words in a relation with an origin mapping, indicating an origin input position for each output position, in a similar way. This defines a general object called origin graph. We characterise the families of origin graphs which corresponds to the semantics of the classical transducer models.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle.
 Seminar MOVE at LIF, February 2nd 2017, Marseille —
Regular transductions with origin semantics
This talk is about regular transductions, which are stringtostring functions realised by one of the following equivalent deterministic formalisms: MSO transduction, twoway transducer and streaming string transducer. We may observe that each of these formalisms provides more than just a function from words to words. Indeed, one can also reconstruct origin information, which says how positions of the output string originate from positions of the input string. It is also possible to provide any stringtostring function with an origin semantic, indicating an origin input position for each output position, in a similar way. This defines a general object, that extends functions and which we call origin graph. The main result of the talk is a characterisation of the families of origin graphs which correspond to a regular transduction with origin information.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle.
 Seminar at Di – unimi, January 17th 2017, Milano —
On rational and regular transductions
In this talk, I will introduce the model of transducers, which are finite automata extended with the ability to produce output words, making them able to compute stringtostring functions or relations. Contrary to the case of automata, the different variants (1way or 2way, deterministic or not) of the finitememory device leads to different recognition powers.
In a first time, I will present a computational map of the different versions, giving some examples of relevant relations and known results. Then, I will focus on 2way deterministic transducers with origin semantics. This semantic somehow detail the recognized function, by providing for each position of the output, the position of the input from which it was produced. So define, the objects that we consider are extensions of functions, which we can represented as particular graphs. It is then possible to characterize recognizable families of such graphs, by logic and graph properties.
This is recent joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle.
 Seminar Automata at MIMUW, November 23th 2016, Warszawa —
On two way nondeterministic transducers
Transducers are natural extensions of automata aimed to produce an output string from an input string. Though 1way and deterministic (or functional) 2way cases are wellcharacterized, very few results are known about the 2way nondeterministic case.
In this talk, I will introduce some natural algebraic operations on binary relations on words, that attempt to mimic the behavior of 2way transducers. I will prove that these operations are sufficient to characterize the relations realized by some natural subfamilies of 2way nondeterministic transducers (such as rotating, sweeping or unary 2way transducers), but that they do not capture all the abilities of 2way transducers.
 DLT 2016, July from 25th to 28th 2016, Montréal —
Both ways rational functions
We consider binary relations on words which can be recognized by finite twotape 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.
 My PhD defense, May 30th 2016, Paris — manuscript , slides
 École Jeunes Chercheurs en Informatique Mathématique, April 48, Strasbourg −
 GT ALGA − Annual Meeting 2016, April 11 & 12, LIF, Marseille
 Colloque en l’honneur de MarcelPaul Schützenberger in LaBRI, March 2125, Bordeaux −
 Seminar Automate at Irif, February 12 2016, Paris −
On twoway 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 writeonly 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 oneway deterministic (1DT
), oneway nondeterministic (1NT
), twoway deterministic (2DT
), and twoway 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 the2NT
, 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, June 11th 2015, NiceSophiaAntipolis:
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.
 ÉJCIM, Orléans, April 2nd 2015 —
 ICTCS, Pérouse, Septembre 17th 2015 —
 MFCS 2014, Budapest, August 15th 2014 —
 Seminar at DI, Milan, July 2nd 2014 —
 Séminaire Thésards (LIAFA & PPS), Paris, January 22nd 2014
 Seminar in Rouen, 28 Novembre 2013 —
 Journée de rentrée de l’équipe Automate (LIAFA), Paris, October 11th 2013 —
 Journée des entrants (LIAFA), Paris, October 10th 2012 —
 ÉJCIM, Rennes, March 19th 2012 —
Research
Research interest
For a few years I focused my research on twoway automata and extensions, in particular twoway transducers.
Current work
I am currently working on twoway transducers with origin semantic, with Laure Daviaud, Vincent Penelle and Mikołaj Bojańczyk. In parallel, I work on some extensions of MSO logic with, also, ശ്രീജിത്ത് എ വി Sreejith A V and Thomas Zeume. With Olivier Carton and Fabian Reiter I work on the links between a new model of distributed automata and some special counter machines.
Keywords
 automata theory
 verification
 transducers
 formal languages
 computational complexity
 descriptive complexity
 descriptional complexity
 reversibility
 algebra
 logic
Past work and details
 on the one hand I try to describe the descriptive power of nonclassical model of automata. Such descriptions may be obtained by considering some logic fragments or some algebraic operations.
With Christian Choffrut, starting with [CG14], we studied some operations on binary relations of words (or, more generally, on formal power series with coefficient in the free monoids), which are aimed to describe the behavior of twoway transducers (
resp.
twoway weighted automata): the Hadamard product ( concatenation of outputs associated to the same input in two relations,
i.e.
, R ∘ S := {(u, w)∣w = vv′, (u, v)∈R, (u, v′) ∈ S} ) describes the ability to read several time the input, from left to right;  the Hadamard star ( concatenation of an arbitrary number of outputs associated to the same input in a relation,
i.e.
, R^{⋆} := {(u, w)∣w = v_{1}v_{2}⋯v_{n}, each (u, v_{i})∈R} ) mimics the ability to restart a transducer from the begining, thus appending new output to the previously computated ones;  the mirror operation ( pairs obtained from the elements of the relation by taking the reverse of the first component,
i.e.
, R^{r} := {(u, v)∣(u^{r}, v)∈R} ) describe the ability to scan the input from right to left.
The family of Hadamard relations, denoted
Had
, is hence the closure under Hadamard product and Hadamard star of the family of rational relations (denotedRat
). Adding the mirror operation leads to a superfamily, called MirrorHadamard (MHad
). We can show that these operations are sufficient to describe some subfamilies of twoway transducers, as summarized in the following table.  the Hadamard product ( concatenation of outputs associated to the same input in two relations,
 On the other hand, I am interested in the descriptional complexity of simple model. This lead me to consider the cost, in terms of size (
e.g
, the number of states or of transitions), of some simulations.I worked on the famous problems of Sakoda and Sipser (1968), who conjectured that the simulations of twoway nondeterministic finite automata by twoway deterministic or by oneway nondeterministic finite automata has an exponential cost, that is, twoway nondeterministic automaton are exponentially more succinct than the other versions (see [GGP14]).
Publications
Journals

Abstract. In a previous paper we showed that twoway (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.
(The original publication is available at www.edpsciences.org/ita.)

The question of the statesize cost for simulation of twoway nondeterministic automata (2nfas) by twoway 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 twoway 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 selfverifying, 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.
Conferences

We study various models of transducers equipped with origin information. We consider the semantics of these models as particular graphs, called origin graphs, and we characterise the families of such graphs recognised by streaming string transducers.

We consider binary relations on words which can be recognized by finite twotape 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.

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

Twoway transducers are ordinary finite twoway automata that are provided with a oneway writeonly tape. They perform a word to word transformation. Unlike oneway 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 twoway unary transducers are no more powerful than oneway transducers.

Twoway transducers are ordinary finite twoway automata that are provided with a oneway writeonly tape. They perform a word to word transformation. Unlike oneway 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 twoway unary transducers are no more powerful than oneway transducers.

The question of the statesize cost for simulation of twoway nondeterministic automata (2nfas) by twoway 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 twoway 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 selfverifying, 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.
Submitted

We prove that MSO on ωwords becomes undecidable after adding a secondorder predicate “set of positions X is ultimately periodic”. We obtain it as a corollary of the undecidability of MSO on ωwords extended with the following secondorder predicate: U₁(X) says that the distance between consecutive positions in a set X⊆ℕ is unbounded. This is achieved by showing that adding U₁ to MSO gives a logic with the same expressive power as MSO+U, a logic on ωwords with undecidable satisfiability.
Others

 Which classes of origin graphs are generated by transducers? Preprint (long version) 2017 — .

The question of the statesize cost for simulation of twoway nondeterministic automata (2NFAs) by twoway 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 twoway 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 selfverifying, 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.
Teaching
De 2012 à 2016 j’ai enseigné en Licence et en Master d’Informatique (travaux dirigés, travaux pratiques) à l’Université Paris Diderot (Paris 7).
M1XML
— commeXML
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 desdtd
et des schémaxsd
. Puis on débouche sur de l’analyse avec des schématrons et surtoutxslt
, 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 enjava
(2011 et 2013)
Links
Computerscientific friendship
 AnnaCarla Russo
 Ioana Cristescu
 Giovanna Lavado
 Étienne Miquey
 Florent Capelli
 Pierre Guillon
 Simon Martiel
 Alex Bredariol Grilo
 Fabian Reiter
 Bruno Karelovic
 Thibault Godin
 Charles Paperman
 Michaël Cadilhac
 Luc Dartois
 Nathanaël Fijalkow
 Luca Prigioniero
 Jehanne Dousse
 Sreejith
 Thomas Picchetti
 Vincent Penelle
 Laure Daviaud
 Thomas Zeume
Advertising
 Crowd Event is almost an application that helps artists, scenes (pubs) and public to be connected.
 Jeanne Guillon et Aurélien Delsaux font entreautre du Théâtre d’Art pour Tous : l’Arbre.
 Catherine Prady translates french2english.
 La cyclofficine d’IvrysurSeine, a nice place to fix your bike.
Tools
 Firefox is a famous open web browser which enjoys
 Vimperator (which can be boosted by Pterosaur) to have vimlike functionalities (that we can also find in the minimalist Vimb web browser),
 uBlock, to block advertising,
 tree Style Tab, to display tabs as a tree,
 Markdown Here, to compile Markdown syntax into plain html (in particular in mails),
 Markdown Viewer, to preview Markdown files,
 DuckDuckGo and its !, to privately and efficiently search on the web.
 I highlight
 OpenStreetMap,
 OpenRouteService, to find the best itinerary (bike!),
 Météo dans l’heure, to avoid rain on short bike travel,
 Wikipedia, of course,
 Trello, to help collaborations,
 Qwant, to securely search on the web,
 Capitaine Train, for traveling by train and coach in Europe (mainly in France).
 As a convinced Linux user, I emphasis
Culture and 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.
 Cette vidéo à la qualité pédagogique exemplaire nous présente les faiblesses de nos systèmes de votes et étudie des alternatives.