Sylvain Schmitz

Assistant professor

Algorithmic Applications of wqos

I've been busy these last few years trying to get a clear picture of the complexity of problems that arise from the use of well-quasi-orders and well-structured transition systems. Here is some of the material I co-authored on the subject:


Verification, infinite systems, well quasi orders, formal languages, parsing, computational linguistics

Recent Publications

Th. Colcombet, M. Jurdziński, R. Lazić and S. SchmitzPerfect Half Space GamesIn LICS'17, pages 1-11. IEEE Press, June 2017. Web page | BibTeX )
B. Bérard, S. Haar, S. Schmitz and S. SchwoonThe Complexity of Diagnosability and Opacity Verification for Petri NetsIn PETRI NETS'17, LNCS 10258, pages 200-220. Springer, June 2017. Web page | BibTeX )
J. Goubault-Larrecq and S. SchmitzDeciding Piecewise Testable Separability for Regular Tree LanguagesIn ICALP'16, Leibniz International Proceedings in Informatics 55, pages 97:1-97:15. Leibniz-Zentrum für Informatik, July 2016. Web page | BibTeX )
R. Lazić and S. SchmitzThe Complexity of Coverability in ν-Petri NetsIn LICS'16, pages 467-476. ACM Press, July 2016. Web page | BibTeX )
D. Baelde, S. Lunel and S. SchmitzA Sequent Calculus for a Modal Logic on Finite Data TreesIn CSL'16, Leibniz International Proceedings in Informatics 62, pages 32:1-32:16. Leibniz-Zentrum für Informatik, September 2016. Web page | BibTeX )

Full BibTeX

More publications...

Recent Talks

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

More talks...

Other activities

Teaching (2016–2017)

ESSLLI 2016, Bolzano-Bozen
Course on Algorithmic Aspects of WQO Theory together with Ph. Schnoebelen.
MPRI, Paris
First half of the logical and computational structures for linguistic modelling lectures.
Tree automata, techniques and applications lectures.
Computer science option of the French "agrégation de mathématiques", ENS Cachan
Lectures on formal languages and automata.
Second half of the lectures on logic.
Bachelor of computer science, ENS Cachan
Lectures in formal languages.
Department of doctoral studies, ENS Cachan
Tutorial on searching and publishing on the web

Further documents and course pages related to my older teaching activities can be found in my teaching activities page.

About LSV


Export in vCard format

Sylvain Schmitz
LSV, CNRS & ENS de Cachan
61, avenue du Président Wilson
94235 CACHAN Cedex, France
+33 (0)1 47 40 75 42
+33 (0)1 47 40 75 21
+33 (0)1 47 40 75 20