60 citations · 60 across the 1 of their papers we have counts for
Showing cs.LOShow all
3 papers · 1 filter
cs.LO2019
Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
Jérôme Leroux, Sylvain Schmitz
The reachability problem in vector addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problem…
cs.LO2019
Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete
Petr Jančar, Sylvain Schmitz
Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity up…
cs.LO2011★ 60 cited
Multiply-Recursive Upper Bounds with Higman's Lemma
Sylvain Schmitz, Philippe Schnoebelen
We develop a new analysis for the length of controlled bad sequences in well-quasi-orderings based on Higman's Lemma. This leads to tight multiply-recursive upper bounds that readi…