107 citations · 401 across the 20 of their papers we have counts for
23 papers
On arch factorization and subword universality for words and compressed words
Philippe Schnoebelen, Julien Veron
Using arch-jumping functions and properties of the arch factorization of words, we propose a new algorithm for computing the subword circular universality index of words. We also i…
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 Functions Weakly Computable by Pushdown Petri Nets and Related Systems
J. Leroux, M. Praveen, Ph. Schnoebelen +1
We consider numerical functions weakly computable by grammar-controlled vector addition systems (GVASes, a variant of pushdown Petri nets). GVASes can weakly compute all fast growi…
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…
On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders
Mirna Džamonja, Sylvain Schmitz, Philippe Schnoebelen
We investigate the ordinal invariants height, length, and width of well quasi orders (WQO), with particular emphasis on width, an invariant of interest for the larger class of orde…
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…
On the state complexity of closures and interiors of regular languages with subwords and superwords
Prateek Karandikar, Matthias Niewerth, Philippe Schnoebelen
The downward and upward closures of a regular language are obtained by collecting all the subwords and superwords of its elements, respectively. The downward and upward interio…
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…
On the index of Simon's congruence for piecewise testability
Prateek Karandikar, Manfred Kufleitner, Philippe Schnoebelen
Simon's congruence, denoted \sim_n, relates words having the same subwords of length up to n. We show that, over a k-letter alphabet, the number of words modulo \sim_n is in 2^{Θ(n…
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…
Toward a Compositional Theory of Leftist Grammars and Transformations
Pierre Chambart, Philippe Schnoebelen
Leftist grammars [Motwani et al., STOC 2000] are special semi-Thue systems where symbols can only insert or erase to their left. We develop a theory of leftist grammars seen as wor…
Undecidability of performance equivalence of Petri nets
Slawomir Lasota, Marcin Poturalski
We investigate bisimulation equivalence on Petri nets under durational semantics. Our motivation was to verify the conjecture that in durational setting, the bisimulation equivalen…
On Termination for Faulty Channel Machines
Patricia Bouyer, Nicolas Markey, Joël Ouaknine +2
A channel machine consists of a finite controller together with several fifo channels; the controller can read messages from the head of a channel and write messages to the tail of…
On computing fixpoints in well-structured regular model checking, with applications to lossy channel systems
C. Baier, N. Bertrand, Ph. Schnoebelen
We prove a general finite convergence theorem for "upward-guarded" fixpoint expressions over a well-quasi-ordered set. This has immediate applications in regular model checking of…
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…