Sylvain Schmitz

Associate professor, ENS Cachan

Algorithmic Aspects of WQO Theory

Together with Ph. Schnoebelen, I taught a course at ESSLLI 2012 in Opole on the algorithmic aspects of wqo theory from August 6th to August 10th, 2012.

Here you can find the

material

for this course.

Research

Keywords: Verification, infinite systems, wqo, formal languages, parsing, computational linguistics

Publications

Most recent work:

The Power of Priority Channel Systems: Joint work with C. Haase and Ph. Schnoebelen. We introduce priority channel systems, a new class of channel systems where messages carry a numeric priority, and where higher priority messages can supercede lower priority ones preceding them in the fifo communication buffers. Such systems can be used to model differentiated service protocols, where packet dropping policies in congested networks rely on priorities to maintain the quality of service for important messages. We prove that safety and inevitability properties are decidable in priority channel systems, and that their computational complexity is complete for F_ε₀.
Model Checking Parse Trees: Joint work with A. Boral from CMI. We consider a variant of the satisfiability of PDL formulae on trees (or equivalently of Regular XPath), in presence of a tree language. The main originality is that the tree languages we consider are the set of parse trees (or parse forest) of a given word according to a context-free grammar. We show that this problem has applications in computational linguistics and for declarative syntactic specifications of programming languages, and study its computational complexity. Will be presented at LICS 2013.
The Parametric Ordinal-Recursive Complexity of Post Embedding Problems: Joint work with P. Karandikar from CMI. We refine the complexity lower bounds of Chambart and Schnoebelen to parametric bounds for Post Embedding Problems. Was presented at FoSSaCS 2013.
On LR Parsing with Selective Delays: Joint work with E. Bertsch from the Ruhr-Universität Bochum and M.-J. Nederhof from the University of St Andrews. We propose a selective version of Marcus-Leermakers parsing, and provide two characterizations for the resulting class of grammars: one via grammar transformations, the other via a direct parser construction. Was presented at CC 2013.

Full BibTeX

More publications...

Talks

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.
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.
LICS 2012, 9am, June 28th, 2012, room B04, Dubrovnik, Croatia.: I 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.