Shorty

• Journées ALGA & Vérif, May 29–31 2017, Créteil — Abstract

  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.

• ICALP 2017, July 10–14 2017, Warszawa

Previously

• Dagstuhl seminar, April 02–05 2017, Leibniz —
• Seminar Automata at MIMUW, February 15th 2017, Warszawa — Abstract

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

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

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

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

  Both ways rational functions

  [Bruno Guillon][bguil] (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

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 = v₁v₂⋯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 (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.

  

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

Submitted

• Mikołaj Bojańczyk Laure Daviaud Bruno Guillon Vincent Penelle
  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.

  Accepted at ICALP 2017.
• Mikołaj Bojańczyk Laure Daviaud Bruno Guillon Vincent Penelle Sreejith A V
  Undecidability of MSO+“ultimately periodic”

  We prove that MSO on ω-words becomes undecidable after adding a second-order 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 second-order 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.

  Submitted at CSL 2017.

Others

• 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 —
• Internships

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

Computer-scientific friendship

• Anna-Carla 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 entre-autre du Théâtre d’Art pour Tous : l’Arbre.
• Catherine Prady translates french2english.
• La cyclofficine d’Ivry-sur-Seine, a nice place to fix your bike.

Tools

• Firefox is a famous open web browser which enjoys a multitude of extensions.:
  • Vimperator (which can be boosted by Pterosaur) to have vim-like 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 some free open online services.:
  • 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 some programs and tricks.:
  • meld, nice tool to compare files and directories,
  • rsync, to synchronize files and folders even remote ones,
  • CDPATH, an environment variable that extend your local bash navigation to a list of directories,
  • mercurial et git, to safely manage your projects.

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.

Me online

Affiliation