60 citations · 60 across the 2 of their papers we have counts for
4 papers
On flat lossy channel machines
Philippe Schnoebelen
We show that reachability, repeated reachability, nontermination and unboundedness are NP-complete for Lossy Channel Machines that are flat, i.e., with no nested cycles in the cont…
The Ideal Approach to Computing Closed Subsets in Well-Quasi-Ordering
Jean Goubault-Larrecq, Simon Halfon, Prateek Karandikar +2
Elegant and general algorithms for handling upwards-closed and downwards-closed subsets of WQOs can be developed using the filter-based and ideal-based representation for these set…
On shuffle products, acyclic automata and piecewise-testable languages
Simon Halfon, Philippe Schnoebelen
We show that the shuffle $L \unicode{x29E2} F$ of a piecewise-testable language and a finite language is piecewise-testable. The proof relies on a classic but little-used a…
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…