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: 03/2018).
Contact
Events
Shortly
 DLT, September 10–14 2018, Tokyo –
Twoway Automata and OneTape Machines Read Only versus Linear Time
It is wellknown that onetape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of nondeterministic finite automata into equivalent lineartime onetape deterministic machines. We prove a polynomial blowup from twoway nondeterministic finite automata into equivalent weightreducing onetape deterministic machines that work in linear time. The blowup remains polynomial if the tape in the resulting machines is restricted to the portion which initially contains the input. However, in this case the machines resulting from our construction are not weight reducing, unless the input alphabet is unary.
 Highlights of Logic, Games and Automata, September 18–21 2018, Berlin –
Determinizing twoway automata with lineartime Turing machines
In 1968, Sakoda and Sipser conjectured that the simulation cost of the determinization of twoway automata is exponential in the worst case. In spite of all attempts the problem remains open today. In this work we propose a new approach, in which the simulating deterministic machine has further abilities besides the readonly capacity of twoway automata. We prove a polynomial sizecost simulation of twoway nondeterministic automata by deterministic weightreducing Turing machines, a syntactical restriction of lineartime Turing machines which recognize regular languages only, as proved by Hennie in 1965. We then discuss the cost of the conversion into weightreducing linearboundedautomata, which constrain the former model by restricting the space to the portion of the tape that initially contain the input word.
This is a joint work with Giovanni Pighizzini, Luca Prigioniero and Daniel Průša that has been presented at DLT’18.
 Journées ALGA (not going), October 2018, Lille
Previously
 NCMA (invited), August 21–22, Košice –
 CIAA, July 30–August 2 2018, Charlottetown –
 DCFS, July 25–27, Halifax
 Autobóz (not going), July 15–21, Pyrénées mountains
 Lipa summer school, June 25–29 2018, Warsaw
 AUTOMATA (not going), June 20–22 2018, Gent
 Séminaire Méthodes Formelles, June 12th 2018, Bordeaux —
Undecidability of MSO+“ultimately periodic”
We prove that MSO on ωwords becomes undecidable if allowing to quantify over sets of positions that are ultimately periodic, i.e., sets X such that for some positive integer p, ultimately either both or none of positions x and x+p belong to X. We obtain it as a corollary of the undecidability of MSO on ωwords extended with the secondorder predicate U₁(X) which says that the distance between consecutive positions in a set X⊆N 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.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud, Vincent Penelle and Sreejith.
 Journées Vérif, May 28–30 2018, Grenoble —
Undecidability of MSO+“ultimately periodic”
We prove that MSO on ωwords becomes undecidable if allowing to quantify over sets of positions that are ultimately periodic, i.e., sets X such that for some positive integer p, ultimately either both or none of positions x and x+p belong to X. We obtain it as a corollary of the undecidability of MSO on ωwords extended with the secondorder predicate U₁(X) which says that the distance between consecutive positions in a set X⊆N 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.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud, Vincent Penelle and Sreejith, which is part of the project LIPA that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.683080).
 Séminaire du LSV, March 13th 2018, Cachan —
Which classes of origin graphs are generated by transducers?
This talk is about regular word transductions, which form a robust class of (partial) functions from (finite) words to (finite) words. Regular transduction are for instance recognized by deterministic 2way finite automata with outputs or deterministic streaming string transducers. We start from the observation that the various equivalent models of transducers capturing the class, actually provide more than a function from words to words. Indeed, one can also reconstruct origin information which says how positions of the output word originate from positions of the input word. With this semantics, transductions are viewed as sets of particular graphs, called origin graphs. This allows us to express properties, such as «the output is a permutation of the input» or «the transduction is a righttoleft oneway transduction», using MSO Logic.
After an introduction presenting the general framework, I will briefly show that MSO Logic is decidable on the origin semantics of regular transducers, yielding procedures to check formulas such as given above. Then, I will characterize the families of origin graphs which corresponds to the semantics of streaming string transducers.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle, which has been published at ICALP17.
This work has been published in proceedings of ICALP 2017. Preprint (long version): . Slides: .
 Seminar day on Automata and Formal Language, November 22th 2017, Milano —
 Verification seminar, November 30th 2017, Oxford —
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 first show that MSO is decidable on the origin semantics of the main transducer models, yielding procedures to check formulas such as «the output is a permutation of the input» or «the transduction is a righttoleft oneway transduction». We then characterise the families of origin graphs which corresponds to the semantics of streaming string transducers.
This is joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle, which has been published to ICALP17.
This work has been published in proceedings of ICALP 2017. Preprint (long version): . Slides: .
 Highlights of Logic, Games and Automata, September 12–15 2017, London
 International training school on reversible computation, August 28–31 2017, Toruń – ICT COST Action IC1405
 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 published at ICALP 2017. Preprint (long version): . Slides: .
 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
 ÉJCIM, April 48 2016, Strasbourg
 Journées ALGA, April 11 & 12 2016, LIF, Marseille
 Colloque en l’honneur de MarcelPaul Schützenberger in LaBRI, March 2125 2016, 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.
 ÉPIT, Fréjus, May 25–29 2015
 É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.
Keywords
 automata theory
 verification
 transducers
 formal languages
 computational complexity
 descriptive complexity
 descriptional complexity
 reversibility
 algebra
 logic
Current work
I am currently working on descriptional complexity of various models extending automata (or equivalently, restricting Turing Machines), with Giovanni Pighizzini and Luca Prigioniero.
I also consider problems connected to reversible computing with Martin Kutrib, Giovanna J. Lavado, Andreas Malcher, Giovanni Pighizzini and Luca Prigioniero. In particular we study reversible pushdown transducers and weaklyirreversible finite automata.
I recently submitted a work with Olivier Carton and Fabian Reiter about connections between a new model of distributed automata (related to cellular automata) and some special counter machines.
In parallel, I am concluding a project on twoway transducers with origin semantics, with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle, including results presented at ICALP’17. I am also considering some extensions of MSO logic with, also, ശ്രീജിത്ത് എ വി Sreejith A V.
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.
Accepted

We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right while incrementing or decrementing a fixed number of counters. The two classes differ in the extra features they offer: one allows to copy counter values, whereas the other allows to compute copyless sums of counters. Our distributed automata, on the other hand, operate on directed path graphs that represent words. All nodes of a path synchronously execute the same finitestate machine, whose state diagram must be acyclic except for selfloops, and each node receives as input the state of its direct predecessor. These devices form a subclass of lineartime oneway cellular automata.

Nonselfembedding grammars are a restriction of contextfree grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size between nonselfembedding grammars and deterministic finite automata is known. The same size gap is also known from constant height pushdown automata and 1limited automata to equivalent deterministic finite automata. Constant height pushdown automata and 1limited automata are compared with nonselfembedding grammars. It is proved that nonselfembedding grammars and constant height pushdown automata are polynomially related in size. However, they can be exponentially larger than 1limited automata.

The time complexity of 1limited automata is investigated from a descriptional complexity point of view. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase of the size, each 1limited automaton can be transformed into an halting lineartime equivalent one. Furthermore the construction preserves determinism. We also obtain polynomial transformations into related models, including weightreducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.

It is wellknown that onetape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of nondeterministic finite automata into equivalent lineartime onetape deterministic machines. We prove a polynomial blowup from twoway nondeterministic finite automata into equivalent weightreducing onetape deterministic machines that work in linear time. The blowup remains polynomial if the tapes in the resulting machines are restricted to the portions which initially contain the input. However, in this case the machines resulting from our construction are not weight reducing, unless the input alphabet is unary.

Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to four types of lengthpreserving transductions as well as to the property of working reversibly. It turns out that accurate to one case separating witness transductions can be provided. For the remaining case it is possible to establish the equivalence of both families by proving that stationary moves can always be removed in lengthpreserving reversible pushdown transductions.
Others


Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted languages are called kreversible automata and kreversible languages, respectively. The existence of kreversible languages which are not (k−1)reversible is known, for each k>1. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are kreversible for some k. Conditions characterizing the class of kreversible languages, for each fixed k, and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not kreversible, but which accepts a kreversible language, into an equivalent kreversible finite automaton, is presented.

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.



We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right while incrementing or decrementing a fixed number of counters. The two classes differ in the extra features they offer: one allows to copy counter values, whereas the other allows to compute copyless sums of counters. Our distributed automata, on the other hand, operate on directed path graphs that represent words. All nodes of a path synchronously execute the same finitestate machine, whose state diagram must be acyclic except for selfloops, and each node receives as input the state of its direct predecessor. These devices form a subclass of lineartime oneway cellular automata.
 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
 Accessibil/mente, writes articles on accessibility for disable persons.
 Crowd Event was 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.