Sylvain Schmitz

Assistant professor

Habilitation Defense

I will defend my habilitation thesis titled Algorithmic Complexity of Well-Quasi-Orders on

Date
Monday, November 27 2017 at 02:00pm
Place
Daniel Chemla amphitheater (Institut d'Alembert)
Speaker
Sylvain Schmitz

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:

Research

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

Recent Publications

M. Dzamonja, S. Schmitz and Ph. SchnoebelenOn the width of FAC orders, a somewhat rediscovered notion, Preprint, 2017. Web page | PDF | BibTeX )
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 )

Full BibTeX

More publications...

Recent Talks

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.
HighlightsI 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, 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ć.

More talks...

Other activities

Teaching (2017–2018)

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 Paris-Saclay
Lectures on the theory of programming languages.
Second half of the lectures in logic.
Bachelor of computer science, ENS Paris-Saclay
First half of the lectures in formal languages.
Tutorials on programming languages.

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

About LSV

Contact

Export in vCard format

Sylvain Schmitz
Address
LSV, CNRS & ENS de Cachan
61, avenue du Président Wilson
94235 CACHAN Cedex, France
Office
RH-B-102
Phone
+33 (0)1 47 40 75 42
Fax
+33 (0)1 47 40 75 21
Secr.
+33 (0)1 47 40 75 20
E-Mail
Sylvain.Schmitz@lsv.ens-cachan.fr

Funding