107 citations · 618 across the 21 of their papers we have counts for
4 papers · 2 filters
Complexity Bounds for Ordinal-Based Termination
Sylvain Schmitz
`What more than its truth do we know if we have a proof of a theorem in a given formal system?' We examine Kreisel's question in the particular context of program termination proof…
The Power of Well-Structured Systems
Sylvain Schmitz, Philippe Schnoebelen
Well-structured systems, aka WSTSs, are computational models where the set of possible configurations is equipped with a well-quasi-ordering which is compatible with the transition…
Implicational Relevance Logic is 2-EXPTIME-Complete
Sylvain Schmitz
We show that provability in the implicational fragment of relevance logic is complete for doubly exponential time, using reductions to and from coverability in branching vector add…
Non-Elementary Complexities for Branching VASS, MELL, and Extensions
Ranko Lazić, Sylvain Schmitz
We study the complexity of reachability problems on branching extensions of vector addition systems, which allows us to derive new non-elementary complexity bounds for fragments an…