Talks

LSV's 20th Anniversary

LSV's 20th Anniversary, 3:15pm, May 12th, 2017, ENS Cachan, Cachan, France.
LSV's 20th Anniversary 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.

Upcoming Talks

Highlights 2017, 15:45pm, September 13th, 2017, Queen Mary University of London, UK.
HighlightsI 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 piecewise-testable separability problems, based on the ICALP'16 paper with J. Goubault-Larrecq.
Gregynog 71717, 10am, July 4th, 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 23rd, room M1.01, Reykjavik University, Iceland
LICSI 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
MIMUWI presented 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 24th, 2017, room 5870, University of Warsaw, Poland
MIMUWI 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 12th, 2017, ENS Cachan, Cachan, France.
LSV's 20th Anniversary 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 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 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 8th, 2016, Université libre de Bruxelles, Brussels, Belgium.
HighlightsI 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. Goubault-Larrecq. Here are the slides.
LICS 2016, 16:11pm, July 6th, 2016, Columbia University, New York, USA.
LICSI 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 Quasi-Orders in Computer Science, 4:30pm, January 21st, 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 7th, 2016, Université Paris-Diderot.
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 3rd, 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 6th, 2015, Kyoto, Japan.
LICSI 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.
The Leverhulme Trust 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 6th, 2015, University of Oxford, Oxford, UK.
The Leverhulme Trust 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 28th, 2015, Queen Mary University of London, London, UK.
The Leverhulme Trust 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 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.
RTA-TLCA 2014, Vienna Summer of Logic, 10:45am, July 14th, 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 1st, 2014, Schloss Dagstuhl, Germany.
Don't Panic!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 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 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 11th, 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 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.
HighlightsI presented a short talk on non-elementary complexity classes. See the paper for in-depth 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.
LICS 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 26th, 2013, Roger Thayer Stone Center for Latin American Studies, Room 204, Tulane University, New Orleans, USA.
LICS I presented the paper Model-Checking 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 in-depth material.
Dahu Seminars, 10:30am, July 5th, 2012, library, LSV, Cachan, France.
I gave a slighlty extended talk on the paper The Ordinal-Recursive Complexity of Timed-Arc 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.
LICSI 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 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 Kick-off Meeting, 2:10pm, December 8th, 2011, LIAFA, Paris, France.
I presented an overview of the current work on Algorithmic Theory of WQOs.
ReacHard Kick-off 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 Model-Checking 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 Rule-Based 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 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.
LICSI 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, 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 Pierre-Cyrille 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 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 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 Context-Free Grammars for Parsing and Verification in presence of the available language theory-savvy 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 Context-Free Grammars. Here are the slides.
LDTA'07, 2:30pm, March 25, 2007, room CP2-111, 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 Shift-Resolve 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 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 help organize in Sophia Antipolis. Here are a (slightly technical) short abstract and the slides of the talk.

About LSV