Bruno Guillon

postdoc at Università degli studi di Milano

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 finite-state recognisability» (ERC project LIPA).

Before that, I was a PhD student in IRIFUniversité Paris Diderot, PARIS VII and in DIUniversità degli studi di Milano.

My Curriculum Vitæ is available here (last update: 04/2017).

Contact

  • bruno.guillon@unimi.it
    • Dipartimento di Informatica
    • Università degli studi di Milano
    • via Comelico, 39
    • 20135 Milano
    • ITALY
    • Room T310

Events

Shorty

Previously

  • ICALP 2017, July 10–14 2017, Warsaw —

    Which classes of origin graphs are generated by transducers?

    Mikołaj Bojańczyk Daviaud Laure Bruno Guillon Vincent Penelle (University of Warsaw)

    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 two-way automata with outputs, streaming string transducers and string-to-string 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 string-to-string 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 (2-way automata with outputs, streaming string transducers, string-to-string MSO-transduction) 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 two-way automata with outputs, streaming string transducers and string-to-string 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 string-to-string functions realised by one of the following equivalent deterministic formalisms: MSO transduction, two-way 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 string-to-string 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 string-to-string functions or relations. Contrary to the case of automata, the different variants (1-way or 2-way, deterministic or not) of the finite-memory 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 2-way 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 1-way and deterministic (or functional) 2-way cases are well-characterized, very few results are known about the 2-way nondeterministic case.

    In this talk, I will introduce some natural algebraic operations on binary relations on words, that attempt to mimic the behavior of 2-way transducers. I will prove that these operations are sufficient to characterize the relations realized by some natural subfamilies of 2-way nondeterministic transducers (such as rotating, sweeping or unary 2-way transducers), but that they do not capture all the abilities of 2-way transducers.

  • DLT 2016, July from 25th to 28th 2016, Montréal —

    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.

  • My PhD defense, May 30th 2016, Paris — manuscript , slides
  • École Jeunes Chercheurs en Informatique Mathématique, April 4-8, Strasbourg −
  • GT ALGA − Annual Meeting 2016, April 11 & 12, LIF, Marseille
  • Colloque en l’honneur de Marcel-Paul Schützenberger in LaBRI, March 21-25, Bordeaux −
  • Seminar Automate at Irif, February 12 2016, Paris −

    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, June 11th 2015, Nice-Sophia-Antipolis:

    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 two-way automata and extensions, in particular two-way transducers.

Current work

I am currently working on two-way 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 non-classical 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 two-way transducers (resp. two-way 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 = v1v2vn,  each (u, vi)∈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., Rr := {(u, v)∣(ur, 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 (denoted Rat). Adding the mirror operation leads to a super-family, called Mirror-Hadamard (MHad). We can show that these operations are sufficient to describe some subfamilies of two-way transducers, as summarized in the following table.

    hadtable16-png

  • 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 two-way nondeterministic finite automata by two-way deterministic or by one-way nondeterministic finite automata has an exponential cost, that is, two-way nondeterministic automaton are exponentially more succinct than the other versions (see [GGP14]).

Publications

Have a look to my dblp page .

Journals

  • Bruno Guillon

    Abstract. 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.

    10.1051/ita/2016028

    (The original publication is available at www.edpsciences.org/ita.)

    RAIRO – Theoretical Informatics and Applications504275–2942016
  • Viliam Geffert Bruno Guillon Giovanni Pighizzini

    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.1016/j.ic.2014.08.009
    Inf. Comput.23971–86 2014

Conferences

  • Mikołaj Bojańczyk Laure Daviaud Bruno Guillon Vincent Penelle

    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.

    Preprint (long version) .

    10.4230/LIPIcs.ICALP.2017.114
    ICALP 2017114:1-114:13
  • Christian Choffrut Bruno Guillon

    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 16114-124
  • Bruno Guillon

    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 201591-108
  • Christian Choffrut Bruno Guillon

    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 2014279-283
  • Christian Choffrut Bruno Guillon

    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 2014196–207
  • Viliam Geffert Bruno Guillon Giovanni Pighizzini

    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 2012264–276

Others

    • Mikołaj Bojańczyk Laure Daviaud Bruno Guillon Vincent Penelle Which classes of origin graphs are generated by transducers? Preprint (long version) 2017 — .
    • Viliam Geffert Bruno Guillon Giovanni Pighizzini

      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
    • Communicating Finite Automata System and Tally Languages 2012, Master 2

      report and slides .

    • 2-ways outer-nondeterministic finite automata and descriptional complexity 2011, Master 1

      report and slides .

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).