107 citations · 401 across the 20 of their papers we have counts for
13 papers · 1 filter
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…
Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
Simon Halfon, Philippe Schnoebelen, Georg Zetzsche
We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the theory is undecidable (alrea…
The height of piecewise-testable languages and the complexity of the logic of subwords
Prateek Karandikar, Philippe Schnoebelen
The height of a piecewise-testable language is the maximum length of the words needed to define by excluding and requiring given subwords. The height of is an important…
Decidability in the logic of subsequences and supersequences
Prateek Karandikar, Philippe Schnoebelen
We consider first-order logics of sequences ordered by the subsequence ordering, aka sequence embedding. We show that the Σ_2 theory is undecidable, answering a question left open…
On Reachability for Unidirectional Channel Systems Extended with Regular Tests
Jancar Petr, Prateek Karandikar, Philippe Schnoebelen
"Unidirectional channel systems" (Chambart & Schnoebelen, CONCUR 2008) are finite-state systems where one-way communication from a Sender to a Receiver goes via one reliable and on…
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…
The Power of Priority Channel Systems
Christoph Haase, Sylvain Schmitz, Philippe Schnoebelen
We introduce Priority Channel Systems, a new class of channel systems where messages carry a numeric priority and where higher-priority messages can supersede lower-priority messag…
Solving Stochastic Büchi Games on Infinite Arenas with a Finite Attractor
Nathalie Bertrand, Philippe Schnoebelen
We consider games played on an infinite probabilistic arena where the first player aims at satisfying generalized Büchi objectives almost surely, i.e., with probability one. We pro…
Generalized Post Embedding Problems
Prateek Karandikar, Philippe Schnoebelen
The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining dire…
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…
Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma
Diego Figueira, Santiago Figueira, Sylvain Schmitz +1
Dickson's Lemma is a simple yet powerful tool widely used in termination proofs, especially when dealing with counters or related data structures. However, most computer scientists…
Verifying nondeterministic probabilistic channel systems against -regular linear-time properties
Christel Baier, Nathalie Bertrand, Philippe Schnoebelen
Lossy channel systems (LCSs) are systems of finite state automata that communicate via unreliable unbounded fifo channels. In order to circumvent the undecidability of model checki…