Talks
Upcoming Talks
 IRIF Seminar, February 7, 2019, 1pm, room 3052, Université ParisDiderot, France.
 TBA
 Seminar of the Centre Fédéré en Vérification, February 22, 2019, 1:30pm, NO5, Solvay Room, Université libre de Bruxelles, Belgium.
 TBA
 12th Panhellenic Logic Symposium, June 2019, Anogeia, Crete, Greece.
 TBA
Past Talks
2019
 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 (epsilonpopping) 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 firstorder 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 will cover some work in progress with Petr Jančar. Using a recent reformulation of the proofs for checking bisimulation equivalence as a black box, I will show how to provide Ackermannian upper bounds for the crucial step, which is the computation of a socalled `candidate basis'. This entails that the decision problem itself is Ackermanncomplete, 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 wellquasiorders 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é ParisDiderot, France.
 I presented a talk on the algorithmic complexity of wellquasiorders based on my Habilitation defense. Here are the slides.
2017
 Habilitation defense, 2pm, November 27, 2017, Daniel Chemla amphitheater, ENS ParisSaclay, France
 I defended my habilitation thesis titled Algorithmic Complexity of WellQuasiOrders.
 Day on Resourceaware Strategic Reasoning in Multiagent 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 resourceaware logics. Here are the slides.
 Highlights 2017, 3:45pm, September 13, 2017, Queen Mary University of London, UK.
 I presented the LICS 2017 paper 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 piecewisetestable separability problems, based on the ICALP'16 paper with J. GoubaultLarrecq.
 Gregynog 71717, 10am, July 4, 2017, Gregynog, Wales

I presented a dual approach to the backward coverability algorithm in wellstructured transition systems, using ideal decompositions of downwardsclosed 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 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
 I presented an approach to solving separability by piecewisetestable sets using ideal decompositions. The talk was based on a joint paper with J. GoubaultLarrecq 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 downwardclosures using ideal decompositions. The talk was based on a joint paper with J. GoubaultLarrecq published at ICALP last year.
 LSV's 20th Anniversary, 3:15pm, May 12, 2017, ENS Cachan, Cachan,
France.

A typical application of wellquasiorders is program termination, which can be shown by mapping any execution sequence of a program to a socalled 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 wellquasiorders 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 paper and the slides.
 ICALP 2016, 11:45am, July 12, 2016, Sapienza University, Rome, Italy.
 I presented the paper Deciding Piecewise Testable Separability for Regular Tree Languages written with J. GoubaultLarrecq. Here are the slides.
 LICS 2016, 16:11pm, July 6, 2016, Columbia University, New York, USA.
 I presented the 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 preprint and 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 preprint and the slides.
 Dagstuhl Seminar 16031 Well QuasiOrders in Computer Science, 4:30pm, January 21, 2016, Schloss Dagstuhl, Germany.
 Wellquasiorders 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é ParisDiderot, 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 reproven 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 wellquasiorders. 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é ParisDiderot.
 Chalk talk on ideals of wellquasiorders. These irreducible downwardsclosed sets of elements were first invented in the 1970's but rediscovered in recent years in the theory of wellstructured transition systems, notably by Finkel and GoubaultLarrecq. Ideals provide indeed finite effective representations of downwardsclosed sets, in the same way as bases of minimal elements provide representations of upwardsclosed 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 piecewisetestable separability in the light of ideals. This seminar was also a warmup 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
fastgrowing 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 downwardclosed
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 interreductions 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 2EXPTIMEComplete. Here are the slides.
 Chocola Seminar, 10:30am, October 16, 2014, ENS Lyon, France.
 A chalk talk based on the paper NonElementary 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.
 RTATLCA 2014, Vienna Summer of Logic, 10:45am, July 14, 2014, Informatikhörsaal, TU Vienna, Austria.
 I presented the paper Implicational Relevance Logic is 2ExpTimeComplete. Here are the slides.
 Dagstuhl Seminar 14141 Reachability Problems for InfiniteState Systems, 9am, April 1, 2014, Schloss Dagstuhl, Germany.
 I presented a onehour survey on nonelementary complexity classes. See the paper for indepth 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 nonelementary complexity classes and problems, mostly on subrecursive hierarchies with a few words on
length function theorems
for wellquasiorderings. 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 nonelementary 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 nonelementary complexity classes. See the paper for indepth 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 HTMLbased impress.js, but my slides do not work so well except with Chrome on a highend 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 ModelChecking 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 indepth material.
 Dahu Seminars, 10:30am, July 5, 2012, library, LSV, Cachan, France.
 I gave a slighlty extended talk on the paper The OrdinalRecursive Complexity of TimedArc Petri Nets, Data Nets, and Other Enriched Nets written with S. Haddad and Ph. Schnoebelen.
 LICS 2012, 9am, June 28, 2012, room B04, Dubrovnik, Croatia.
 I presented the paper The OrdinalRecursive Complexity of TimedArc 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 Kickoff Meeting, 2:10pm, December 8, 2011, LIAFA, Paris, France.
 I presented an overview of the current work on Algorithmic Theory of WQOs.
 ReacHard Kickoff Meeting, 5pm, December 6, 2011, LSV, Cachan, France.
 I presented an overview of the current work on Algorithmic Theory of WQOs.
 MFCS 2011, 4pm, August 25, 2011, University of Warsaw, Warsaw, Poland.
 I presented the paper ModelChecking 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 my short paper A Note on Sequential RuleBased 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 MultiplyRecursive 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 PrimitiveRecursive 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, MarnelaVallée, France.
 Upper bounds on Dickson's Lemma, again! OK, I slightly changed the 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.
 INFINI working group, 2pm, February 22, 2011, Library, ENS Cachan, France.
 A presentation of the new results on complexity upper bounds on Higman's Lemma obtained with Ph. Schnoebelen.
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.
 INFINI working group, 2pm, February 2, 2010, Library, ENS Cachan, France.

A survey of complexity and decidability problems for BVAS and related formalisms, with an introduction to their use in computational linguistics.
 INFINI working group, 4pm, November 10, 2009, Library, ENS Cachan, France.

A presentation of a proof of decidability of language boundedness for WSTS.
2009
 CIAA'09, 2pm, July 15, 2009, NICTA's Neville Roach Laboratory, Sydney, Australia.

I presented the paper written with PierreCyrille Héam and Cyril Nicaud on the Random Generation of Deterministic Tree (Walking) Automata. Here are the slides.
 INFINI working group, 2pm, June 2, 2009, Library, ENS Cachan, France.

A presentation of a proof of decidability of language boundedness for Petri nets.
 INFINI working group, 2pm, February 3, 2009, Library, ENS Cachan, France.

A presentation of the proof of decidability of CFL inclusion when one of the grammars has a bounded language, a result due to Ginsburg and Spanier, 1964.
2008
 INFINI working group, 2pm, October 7, 2008, Library, ENS Cachan, France.

A talk on grammar verification.
 LSV Seminars, 11am, September 23, 2008, Pavillon des jardins, ENS Cachan, France.

An updated presentation on the test suite generation project.
 NaTAL Workshop, 12am, June 25, 2008, LORIA, room B011, Nancy, France.
 Just like other error mining techniques, mining for overgeneration 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 twolevel syntax for TAGs, with the usual emphasis on surface realization and overgeneration.
 Systèmes à
événements discrets, 2:30pm, April 28, 2008, LIAFA,
sousmarin, 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 paper. (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.
2007
 TAL Seminars, 2pm, October 18, 2007, room A006, LORIA, Nancy, France.
 Same Ph.D. talk for the NLP crowd here and the students of Nancy's Computational Linguistics Masters.
 Ph.D. defense, 1:30pm, September 24, 2007, conference room, I3S
Laboratory, Sophia Antipolis, France.
 My Ph.D. presentation; thanks to all attendees!
 RECIF/MC3 seminars, 1:45pm, September 20, 2007, meeting room, I3S
Laboratory, Sophia Antipolis, France.
 Ph.D. rehearsal on Approximating ContextFree Grammars for Parsing and Verification in presence of the available language theorysavvy fews, teammates, and three students from ENS. Here are the slides.
 ICALP'07, 12:30am, July 12, 2007, small western lecture hall (SW), Uniwersytet Wrocławski, Wrocław, Poland
 I presented my paper Conservative Ambiguity Detection in ContextFree Grammars. Here are the slides.
 LDTA'07, 2:30pm, March 25, 2007, room CP2111, Universidade do Minho, Braga, Portugal.

I presented my 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 our paper ShiftResolve Parsing: Simple, Linear Time, Unbounded Lookahead. Here are the slides.
 DLT'06,
2:30pm, June 26, 2006, UCSB,
Santa Barbara, California.

I presented my 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
bottomup parsers at this theoretical computer science summer school.
Here are the slides.
 3^{rd} 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 help organize in
Sophia Antipolis. Here are a (slightly technical) short abstract and the slides of the talk.