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: 03/2018).

Contact

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

Events

Shorty

Previously

  • 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 2-way 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 right-to-left one-way 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 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 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 right-to-left one-way 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?

    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 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 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
  • ÉJCIM, April 4-8 2016, Strasbourg
  • Journées ALGA, April 11 & 12 2016, LIF, Marseille
  • Colloque en l’honneur de Marcel-Paul Schützenberger in LaBRI, March 21-25 2016, 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.

  • É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 two-way automata and extensions, in particular two-way 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 weakly-irreversible 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 two-way 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 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

    • Olivier Carton Bruno Guillon Fabian Reiter

      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 finite-state machine, whose state diagram must be acyclic except for self-loops, and each node receives as input the state of its direct predecessor. These devices form a subclass of linear-time one-way cellular automata.

      Preprint (long version) .

      AUTOMATA 2018
    • Bruno Guillon Luca Prigioniero

      The time complexity of 1-limited 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 1-limited automaton can be transformed into an halting linear-time equivalent one. Furthermore the construction preserves determinism. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.

    • Bruno Guillon Giovanni Pighizzini Luca Prigioniero

      Non-self-embedding grammars are a restriction of context-free 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 non-self-embedding grammars and deterministic finite automata is known. The same size gap is also known from constant height pushdown automata and 1-limited automata to equivalent deterministic finite automata. Constant height pushdown automata and 1-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant height pushdown automata are polynomially related in size. However, they can be exponentially larger than 1-limited automata.

    • Bruno Guillon Giovanna J. Lavado Giovanni Pighizzini Luca Prigioniero

      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 k-reversible automata and k-reversible languages, respectively. The existence of k-reversible 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 k-reversible for some k. Conditions characterizing the class of k-reversible 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 k-reversible, but which accepts a k-reversible language, into an equivalent k-reversible finite automaton, is presented.

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

      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.

    • Olivier Carton Bruno Guillon Fabian Reiter

      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 finite-state machine, whose state diagram must be acyclic except for self-loops, and each node receives as input the state of its direct predecessor. These devices form a subclass of linear-time one-way cellular automata.

      arXiv.org 2018
    • 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).