Talks
LSV's 20th Anniversary
 LSV's 20th Anniversary, 3:15pm, May 12th, 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.
Upcoming Talks
 Highlights 2017, 15:45pm, September 13th, 2017, Queen Mary University of London, UK.
 I will present the LICS 2017 paper Perfect Half Space Games written jointly with Th. Colcombet, M. Jurdziński, and R. Lazić.
Past Talks
2017
 Workshop on Separability Problems, 12:15am, July 14th, 2017, University of Warsaw, 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 4th, 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 23rd, 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 7th, 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 24th, 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 12th, 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 2nd, 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 24th, 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 8th, 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 12th, 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 6th, 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 8th, 2016, LaBRI, Bordeaux.
 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 21st, 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 7th, 2016, Université ParisDiderot.
 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 3rd, 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 6th, 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 1st, 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 26th, 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 6th, 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 28th, 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 22nd, 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 26th, 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 14th, 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 1st, 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 13th, 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 19th, 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 11th, 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 7th, 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 19th, 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 28th, 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 27th, 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 26th, 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 22nd, 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 27th, 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 5th, 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 28th, 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 18th, 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 8th, 2011, LIAFA, Paris, France.
 I presented an overview of the current work on Algorithmic Theory of WQOs.
 ReacHard Kickoff Meeting, 5pm, December 6th, 2011, LSV, Cachan, France.
 I presented an overview of the current work on Algorithmic Theory of WQOs.
 MFCS 2011, 4pm, August 25th, 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 15th, 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 8th, 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.