## Talks

### Upcoming talks

no upcoming talks scheduled

### Past talks

#### 2020

- EJCIM 2020, June 16, 2020, 9:15am, online.

A lecture on complexity upper bounds for reachability in vector addition systems, as part of a course designed together with J. Leroux for this summer school. Here are the slides.

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

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 F_{d}-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, Iceland

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.

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.

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

- Groupe de travail Modélisation et Vérification, 11:00am, December 4, 2014, LaBRI, Bordeaux, France.

A survey of the many guises under which alternating vector addition systems with states have been (re)invented, along with a few complexity results together with J.-B. Courtois, M. Jurdziński, and R. Lazić. Here are the slides. - Séminaire Automates, 2:30pm, November 14, 2014, LIAFA, Paris, France.

A survey of the many guises under which alternating vector addition systems with states have been (re)invented, along with a few complexity results together with J.-B. Courtois, M. Jurdziński, and R. Lazić. Here are the slides. - Groupe de travail Sémantique, 2pm, October 22, 2014, PPS, Paris, France.

A talk based on the paper Implicational relevance logic is 2-EXPTIME-complete. Here are the slides. - Chocola Seminar, 10:30am, October 16, 2014, ENS Lyon, France.

A chalk talk based on the paper Non-elementary complexities for branching VASS, MELL, and extensions with R. Lazić. - RP 2014, 2pm, September 22, 2014, University of Oxford, UK.

Invited talk on the complexity of programs proven to terminate thanks to a ranking function into some ordinal. See the supporting paper, and the slides, which contain a bonus application: the first complexity upper bounds on the reachability problem in vector addition systems! - MFCS 2014, 5pm, August 26, 2014, Budapest, Hungary.

I presented the paper Alternating vector addition systems with states written with J.-B. Courtois. Here are the slides. - RTA-TLCA 2014, Vienna Summer of Logic, 10:45am, July 14, 2014, Informatikhörsaal, TU Vienna, Austria.

I presented the paper Implicational relevance logic is 2-EXPTIME-complete. Here are the slides. - Dagstuhl Seminar 14141 Reachability Problems for Infinite-State Systems, 9am, April 1, 2014, Schloss Dagstuhl, Germany.

I presented a one-hour survey on non-elementary complexity classes. See the paper for in-depth material. - Groupe de travail modélisation et vérification, 11am, March 13, 2014, room 076, LaBRI, Bordeaux, France.

I presented a joint work with C. Haase and Ph. Schnoebelen on priority channel systems. Here are the slides.

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

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.

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

- DIT Seminars, 3:30pm, November 27, 2012, amphithéâtre, ENS Rennes, Ker Lann, France.

I presented a general survey on the algorithmic theory of wqos. Check out the slides, and the related ESSLLI lecture notes for more in-depth material. - LICS 2012, 9am, June 28, 2012, room B04, Dubrovnik, Croatia.

I presented the paper The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets written with S. Haddad and Ph. Schnoebelen. Here are the slides. - Verification Seminar, 11am, April 18, 2012, Department of Computer Science, University of Oxford, UK.

I made a presentation on CTL model checking of coverability graphs for Petri nets. Here are my slides.

#### 2011

- LEA Struco Kick-off Meeting, 2:10pm, December 8, 2011, LIAFA, Paris, France.

I presented an overview of the current work on the algorithmic theory of wqos. Here are the slides. - ReacHard Kick-off Meeting, 5pm, December 6, 2011, LSV, Cachan, France.

I presented an overview of the current work on the algorithmic theory of wqos. Here are the slides. - MFCS 2011, 4pm, August 25, 2011, University of Warsaw, Warsaw, Poland.

I presented the paper Model-checking coverability graphs of vector addition systems written with M. Blockelet. Here are the slides. - FSMNLP 2011, 9am, July 15, 2011, campus de la CCI, Université de Tours, Blois, France.

I presented the short paper A note on sequential rule-based POS tagging. Here are the slides. - ICALP 2011, 2:30pm, July 8, 2011, Room CAB G61, ETH Zürich, Zürich, Switzerland.

I presented the paper Multiply-recursive upper bounds with Higman's Lemma written with Ph. Schnoebelen. Here are the slides. - LICS 2011, 2pm, June 23, 2011, Fields Institute, Toronto, Canada.

I presented the paper Ackermannian and primitive-recursive bounds with Dickson's Lemma written with D. Figueira, S. Figueira, and Ph. Schnoebelen. Here are the slides. - Séminaire 68NQRT, 2:30pm, June 9, 2011, IRISA/INRIA, Rennes, France.

Upper bounds with Higman's Lemma, following the ICALP 2011 paper. Here are the slides. - Séminaire Algo, 2:30pm, March 8, 2011, LIGM, Marne-la-Vallée, France.

Upper bounds on Dickson's Lemma — with a slightly changed presentation to better match the work on Higman's Lemma with Ph. Schnoebelen. - Séminaire Automates, 2:30pm, March 4, 2011, room 1C12, LIAFA, Paris, France.

A new 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.

#### 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

#### 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

- Ph.D. defense, 1:30pm, September 24, 2007, conference room, I3S Laboratory, Sophia Antipolis, France.

My Ph.D. defense; thanks to all attendees! - ICALP'07, 12:30am, July 12, 2007, small western lecture hall (SW), Uniwersytet Wrocławski, Wrocław, Poland

I presented the paper Conservative ambiguity detection in context-free grammars. Here are the slides. - LDTA'07, 2:30pm, March 25, 2007, room CP2-111, Universidade do Minho, Braga, Portugal.

I presented the paper An experimental ambiguity detection tool. Here are the slides.

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