Upcoming talks

no upcoming talks scheduled

Past talks

2019

  • Highlights 2019, September 19, 2019, 10:00am, Warsaw, Poland.
    Invited spotlight talk on reachability in Petri nets and vector addition systems, based on the joint paper Reachability in vector addition systems is primitive-recursive in fixed dimension with J. Leroux. Here are the slides.
  • GandALF 2019, September 3, 2019, 12:00 noon, Bordeaux, France.
    Invited survey on multi-dimensional energy games. Here are the slides.
  • ICALP 2019, July 12, 2019, 10:55am, Patras, Greece.
    Presentation of the paper The parametric complexity of lossy counter machines. Here are the slides.
  • PODS 2019, July 2, 2019, 6:10pm, Veilingzaal, Amsterdam, The Netherlands.
    Presentation of a joint work with David Baelde and Anthony Lick on XPath queries in the real world. Here are the slides.
  • 12th Panhellenic Logic Symposium, June 29, 2019, 10:30am, Anogeia, Crete, Greece.
    Invited talk giving a broad selection of applications of well-quasi-orders in logic: in program verification, proof theory, finite model theory, and database theory. Here are the slides.
  • LICS 2019, June 25, 2019, 4pm, room B, Vancouver, Canada.lics.jpg
    Presentation of a joint work with Jérôme Leroux on primitive-recursive upper bounds for VAS reachability in fixed dimension. Here are the slides.
  • 4th Logic Mentoring Workshop, June 22, 2pm, 2019, Vancouver, Canada.
    A selection of applications of well-quasi-orders in logic: in program verification, proof theory, finite model theory, and database theory, with a few additional words about research projects. Here are the slides.
  • Automata Theory Seminar, May 29, 2019, 2:15pm, room 5050, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland.
    The reachability problem in lossy counter machines is the best-known ACKERMANN-complete problem and has been used to establish most of the ACKERMANN-hardness statements in the literature. This hides however a complexity gap when the number of counters is fixed. I've explained on the blackboard how to close this gap and prove Fd-completeness for machines with d counters, which provides the first known uncontrived problems complete for the fast-growing complexity classes at levels 3 < d < ω. This goes through antichain factorisations of bad sequences and analysing the length of controlled antichains. Here is the paper.
  • SWS Colloquium, April 5, 2019, 2pm, room 111 at MPI-Kaiserslautern with videocast to room 029 at MPI-Saarbrücken, MPI-SWS, Germany.
    The usual talk about the complexity of reachability in vector addition systems, which I use as a motivation for explaining the results on the length of controlled bad sequences in well-quasi-orders and the introduction of fast-growing complexity classes.
  • Séminaire Algo du LIGM, March 26, 2019, 2pm, room 4B125 (Copernic building), Université Paris-Est Marne-la-Vallée, France.
    The usual talk about the complexity of reachability in vector addition systems, which I use as a motivation for explaining the results on the length of controlled bad sequences in well-quasi-orders and the introduction of fast-growing complexity classes. Here are the slides.
  • Seminar of the Centre Fédéré en Vérification, February 22, 2019, 1:30pm, NO-5, Solvay Room, Université libre de Bruxelles, Belgium.
    A more detailed, one hour and a half long tutorial on the complexity of reachability in vector addition systems, the use of length function theorems, and the need for fast-growing complexity classes. Here are the slides.
  • IRIF Seminar, February 7, 2019, 1pm, room 3052, Université Paris-Diderot, France.
    The usual talk about the complexity of reachability in vector addition systems, which I use as a motivation for explaining the results on the length of controlled bad sequences in well-quasi-orders and the introduction of fast-growing complexity classes. Here are the slides.
  • CAALM 2019, 3:50pm, January 21, 2019, Auditorium, Chennai Mathematical Institute, Chennai, India.
    Once more, a talk about reachability in vector addition systems, including some new results on complexity upper bounds obtained jointly with Jérôme Leroux. Here are the slides.

2018

  • Séminaire de l'équipe Méthodes Formelles, 11am, November 13, 2018, LaBRI, Bordeaux, France.
    Following Sénizergues' seminal results twenty years ago on the decidability of language equivalence of deterministic pushdown automata and of (weak) bisimilation equivalence of (epsilon-popping) pushshdown automata, several works have attempted to provide complexity bounds for these problems. For instance, some significant simplifications over the original proofs were provided by Stirling and Jančar, using in particular the formalism of first-order grammars instead of pushdown automata, and resulting in Tower upper bounds for the language equivalence problem in deterministic systems. But no complexity bounds were known for the bisimulation equivalence problem. In this talk, I covered some work in progress with Petr Jančar. Using a recent reformulation of the proofs for checking bisimulation equivalence as a black box, I showed how to provide Ackermannian upper bounds for the crucial step, which is the computation of a so-called `candidate basis'. This entails that the decision problem itself is Ackermann-complete, thanks to a lower bound proven by Jančar a few years ago; this is the first completeness result in this line of work.
  • QuantLA workshop, August 2018, Meissen, Germany.
    The decidability of the reachability problem in vector addition systems is a landmark result in theoretical computer science, with applications in an array of fields ranging from program verification to data logics. I presented the main arguments of the first complexity upper bound for this problem, obtained together with Leroux by analysing the decomposition algorithm invented by Mayr and successively refined by Kosaraju and Lambert. Here are the slides.
  • MoVeP 2018, 1:30pm, July 18, 2018, Cachan, France.
    In this tutorial, I presented how to employ well-quasi-orders to prove the termination of programs, and how to exploit the results on the complexity of their uses, with a particular focus on the reachability problem in vector addition systems. Here are the slides.
  • Infinity 2018, July 9, 2018, satellite of ICALP 2018, Prague, Czech Republic.
    The decidability of the reachability problem in vector addition systems is a landmark result in theoretical computer science, with applications in an array of fields ranging from program verification to data logics. I presented the main arguments of the first known complexity upper bound for this problem, obtained together with Leroux by analysing the decomposition algorithms invented by Mayr and successively refined by Kosaraju and Lambert. Here are the slides.
  • Séminaire automates, 2:30pm, February 9, 2018, IRIF, Université Paris-Diderot, France.
    I presented a talk on the algorithmic complexity of well-quasi-orders based on my habilitation defense. Here are the slides.

2017

  • Habilitation defense, 2pm, November 27, 2017, Daniel Chemla amphitheater, ENS Paris-Saclay, France
    I defended my habilitation thesis titled Algorithmic Complexity of Well-Quasi-Orders. Here are the slides.
  • Day on Resource-aware Strategic Reasoning in Multi-agent Systems: Logic & Games, 2:30pm, October 19, 2017, IBISC, Évry, France.
    I presented a survey on games with discrete resources, including the recent results on perfect half space games with Th. Colcombet, M. Jurdziński, and R. Lazić, but also the connections with games played on vector addition systems and with resource-aware logics. Here are the slides.
  • Highlights 2017, 3:45pm, September 13, 2017, Queen Mary University of London, UK.
    I presented the LICS 2017 paper on perfect half space games written jointly with Th. Colcombet, M. Jurdziński, and R. Lazić.
  • Workshop on Separability Problems, 12:15am, July 14, 2017, University of Warsaw, satellite of ICALP 2017, Warsaw, Poland
    In this invited talk, I presented the wqo viewpoint on piecewise-testable separability problems, based on the ICALP'16 paper with J. Goubault-Larrecq.
  • Gregynog 71717, 10am, July 4, 2017, Gregynog, Wales
    I presented a dual approach to the backward coverability algorithm in well-structured transition systems, using ideal decompositions of downwards-closed sets, and allowing a fine complexity analysis. This is based on a joint paper with R. Lazić.
  • LICS 2017, 11:20am, June 23, room M1.01, Reykjavik University, Icelandlics.jpg
    I presented the paper titled Perfect half space games written jointly with Th. Colcombet, M. Jurdziński, and R. Lazić. Here are the slides.
  • Automata Theory Seminar, 2:15pm, June 7, 2017, room 5870, University of Warsaw, Poland
    Second part of the presentation of an approach to solving separability by piecewise-testable sets using ideal decompositions. The talk was based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
  • Automata Theory Seminar, 2:15pm, May 24, 2017, room 5870, University of Warsaw, Poland
    I presented an approach to computing downward-closures using ideal decompositions. The talk was based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
  • LSV's 20th Anniversary, 3:15pm, May 12, 2017, ENS Cachan, Cachan, France.
    A typical application of well-quasi-orders is program termination, which can be shown by mapping any execution sequence of a program to a so-called bad sequence of longer or equal length: as bad sequences are finite, so are executions, and this shows that the program terminates. I showed how such termination proofs can be instrumented to yield complexity upper bounds, by considering the example of the decomposition algorithm for reachability in vector addition systems. Here are the slides.

2016

  • Verification Seminar, 11am, November 2, 2016, Department of Computer Science, Oxford University, Oxford, UK
    I presented the paper The complexity of coverability in ν-Petri nets written with R. Lazić. Here are the slides.
  • Verification Seminar, 11am, October 24, 2016, IRIF, Paris, France
    I presented the applications of ideals of well-quasi-orders for the verification of vector addition systems, based on the papers Demystifying reachability in vector addition systems and Ideal decompositions for vector addition systems with J. Leroux. Here are the slides.
  • Highlights 2016, 14:51pm, September 8, 2016, Université libre de Bruxelles, Brussels, Belgium.
    I presented a joint work with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the slides.
  • ICALP 2016, 11:45am, July 12, 2016, Sapienza University, Rome, Italy.
    I presented the paper titled Deciding piecewise testable separability for regular tree languages written with J. Goubault-Larrecq. Here are the slides.
  • LICS 2016, 16:11pm, July 6, 2016, Columbia University, New York, USA.lics.jpg
    I presented a joint paper with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the slides.
  • Séminaire de l'équipe Méthodes Formelles, 11am, March 8, 2016, LaBRI, Bordeaux, France.
    I presented a joint work with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the slides.
  • Dagstuhl Seminar 16031 Well Quasi-Orders in Computer Science, 4:30pm, January 21, 2016, Schloss Dagstuhl, Germany.
    Well-quasi-orders provide termination or finiteness arguments for many algorithms, and miniaturised versions can furthermore be employed to prove complexity upper bounds for those algorithms. We have however an issue with these bounds: they go way beyond the familiar complexity classes used in complexity theory. I discussed a definition of complexity classes suitable for the task. In particular, unlike the subrecursive classes they are based on, those classes support the usual notions of reduction and completeness. The talk was based on the article Complexity hierarchies beyond Elementary.
  • Reading Group on Logic, Automata, Algebra and Games, 10:30am, January 7, 2016, Université Paris-Diderot, France.
    Chalk talk on ideals in VAS reachability. The decidability of the reachability problem for vector addition systems is a notoriously difficult result. First shown by Mayr in 1981 after a decade of unsuccessful attempts and partial results, its proof has been simplified and refined several times, by Kosaraju and Lambert, and re-proven by very different techniques by Leroux in 2011. The principles behind the original proof remained however obscure. In this seminar, I presented the ideas behind the algorithms of Mayr, Kosaraju, and Lambert (the KLM algorithm) in the light of ideals of well-quasi-orders. The interest here is that ideals provide a semantics to the structures manipulated in the KLM algorithm, bringing some new understanding to its proof of correctness. This approach is based on a joint work with Jérôme Leroux (LaBRI) presented at LICS'15.

2015

  • Reading Group on Logic, Automata, Algebra and Games, 10:30am, December 3, 2015, Université Paris-Diderot.
    Chalk talk on ideals of well-quasi-orders. These irreducible downwards-closed sets of elements were first invented in the 1970's but rediscovered in recent years in the theory of well-structured transition systems, notably by Finkel and Goubault-Larrecq. Ideals provide indeed finite effective representations of downwards-closed sets, in the same way as bases of minimal elements provide representations of upwards-closed sets. After defining ideals and establishing some of their properties, I illustrated their use in a concrete setting. I presented some recent results by Czerwiński, Martens, van Rooijen, and Zeitoun (FCT'15) on the decidability of piecewise-testable separability in the light of ideals. This seminar was also a warm-up for the next seminar on reachability in vector addition systems.
  • LICS 2015, 11:15am, July 6, 2015, Kyoto, Japan.lics.jpg
    I presented the article Demystifying reachability in vector addition systems written with J. Leroux. Here are the slides.
  • DIMAP Logic Day 2015, 9am, June 1, 2015, University of Warwick, Warwick, UK.
    I presented the recent joint work with J. Leroux on deriving complexity upper bounds for the reachability problem in vector addition systems.
  • DIMAP Seminar, 4pm, May 26, 2015, University of Warwick, Warwick, UK.
    I gave my third Leverhulme Lecture (on the blackboard) on complexity classes beyond Elementary. Using the case of reachability in lossy counter machines as a running example, I sketched the proofs of the complexity lower and upper bounds, and motivated the need for fast-growing complexity classes. The lecture was based mainly on the complexity classes paper.
  • Oxford Verification Seminar, 11am, May 6, 2015, University of Oxford, Oxford, UK.
    I gave my second Leverhulme Lecture on ideal decompositions of downward-closed sets, and in particular on how they provide a new understanding of the structures and computations defined in the reachability algorithms for VAS developped by Mayr (1981), Kosaraju (1982), and Lambert (1992). The lecture is based on a joint paper with J. Leroux. Here are the slides.
  • Theory Seminar, 11am, April 28, 2015, Queen Mary University of London, London, UK.
    I gave my first Leverhulme Lecture on the complexity of provability in systems of substructural logic, more precisely affine or contractive variants of linear logic. The main message is that a lot of insights into algorithmic complexity can be gained through inter-reductions with reachability problems in extensions of vector addition systems. The lecture is based on a joint paper with R. Lazić. Here are the slides.
  • ACTS 2015, 11:45am, February 11, 2015, CMI, Chennai, India.
    I gave a chalk talk on the blackboard on the recent complexity upper bounds obtained with J. Leroux for the reachability problem in vector addition systems. Here are some mostly unreadable (guess you had to be there) slides compiled from photos (many thanks to A. Sangnier for taking these!).

2014

2013

  • LAAG Reading Group, 10:30am, December 19, 2013, room 4068, U. Paris Diderot, Paris, France.
    A whiteboard presentation of non-elementary complexity classes and problems, mostly on subrecursive hierarchies with a few words on “length function theorems” for well-quasi-orderings. Some background material for this talk can be found in this paper and in these lecture notes.
  • Theory Seminar, 11am, December 11, 2013, room CS:404, Queen Mary, London, UK.
    I presented recent work on non-elementary complexity classes and problems. Here are the slides and associated paper.
  • 68nqrt Seminar, 2:30pm, November 7, 2013, Markov room, IRISA, France.
    I presented a survey and some work in progress with J.-B. Courtois on vector addition games. See the slides.
  • Highlights 2013, 4:35pm, September 19, 2013, Buffon building, Université Paris Diderot, France.
    I presented a short talk on non-elementary complexity classes. See the paper for in-depth material.
  • Concur 2013, 3:30pm, August 28, 2013, Facultad de Ciencias Económicas, Salón de actos, University of Buenos Aires, Argentina.
    I presented the paper The power of priority channel systems written together with C. Haase and Ph. Schnoebelen. Here are the slides.
  • LICS 2013, 4pm, June 27, 2013, Roger Thayer Stone Center for Latin American Studies, Room 102, Tulane University, New Orleans, USA.lics.jpg
    I presented a short talk on ongoing work on non elementary complexity classes, using some of the material from App. B of the ESSLLI lecture notes on algorithmic wqo theory. I tried something new with the slides, which was to use HTML-based impress.js, but my slides do not work so well except with Chrome on a high-end machine…
  • LICS 2013, 11:30am, June 26, 2013, Roger Thayer Stone Center for Latin American Studies, Room 204, Tulane University, New Orleans, USA.lics.jpg
    I presented the paper Model-checking parse trees written with A. Boral. Here are the slides.
  • CC 2013, 5:30pm, March 22, 2013, Aula A1, Sapienza, University of Rome, Italy.
    I presented the paper On LR parsing with selective delays written with E. Bertsch and M.-J. Nederhof. Here are the slides.

2012

2011

2010

  • Séminaire du groupe Graphes et Logique, 11am, November 23, 2010, room 76, LaBRI, Bordeaux, France.
    A presentation of the work on complexity upper bounds for controlled versions of Dickson's Lemma with D. Figueira, S. Figueira, and Ph. Schnoebelen. Here are the slides.
  • ACL 2010, 4:45pm, July 12, 2010, Venue A, Hall IX, Uppsala University, Uppsala, Sweden.
    A survey of complexity problems for BVAS.
  • Séminaire LIFO, 2pm, June 28, 2010, Salle de cours E15, Université d'Orléans, France.
    A survey of complexity problems for BVAS. Here are the slides.

2009

  • CIAA'09, 2pm, July 15, 2009, NICTA's Neville Roach Laboratory, Sydney, Australia.
    I presented the paper written with Pierre-Cyrille Héam and Cyril Nicaud on the random generation of deterministic tree (walking) automata. Here are the slides.

2008

  • NaTAL Workshop, 12am, June 25, 2008, LORIA, room B011, Nancy, France.
    Just like other error mining techniques, mining for over-generation issues in a grammar requires a test suite in order to detect failures. I presented the current state of my work (in progress) that aims to generate such a test suite directly from the grammar, in order to explore its quirks and corner cases in an orderly manner.
  • Séminaires de Linguistique Informatique à Bordeaux, 5pm, May 19, 2008, LaBRI, room 076, Bordeaux, France.
    A revamped presentation on two-level syntax for TAGs, with the usual emphasis on surface realization and over-generation.
  • Systèmes à événements discrets, 2:30pm, April 28, 2008, LIAFA, sous-marin, Paris, France.
    A presentation of modular syntax formalisms used for programming languages, and of their verification problems. Parts of the talk is based on the “Modular syntax demands verification” technical report. (slides)
  • MOSTRARE Seminars, 10:30am, April 18, 2008, INRIA building, room W11, Lille, France.
    A seminar on computations using the derivation tree language of a tree adjoining grammar. Half survey of surface realization techniques from tree adjoining grammars, half presentation of the results obtained with Joseph Le Roux. Here are the slides.

2007

2006

  • CIAA'06, 4:00pm, August 23, 2006, Barry Lam Hall, NTU, Taipei, Taiwan.
    I presented the paper Shift-resolve parsing: Simple, linear time, unbounded lookahead written with J. Farré and J. Fortes-Gálvez. Here are the slides.
  • DLT'06, 2:30pm, June 26, 2006, UCSB, Santa Barbara, California.
    I presented the paper Noncanonical LALR(1) parsing. Here are the slides.
  • EJC06, 5pm, May 16, 2006, amphitheater 050, LaBRI, Bordeaux, France.
    I presented an introduction to noncanonical parsing and to the construction of noncanonical parsers from canonical bottom-up parsers at this theoretical computer science summer school. Here are the slides.
  • 3rd PhD seminars, 4:30pm, May 10, 2006, room EN 05, Eurecom Institute, Sophia Antipolis, France
    I presented a short tutorial on noncanonical parsing for the third edition of this monthly event I helped organize in Sophia Antipolis. Here are a (slightly technical) short abstract and the slides of the talk.