107 citations · 401 across the 20 of their papers we have counts for
6 papers · 1 filter
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 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 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…
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…
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…