48 citations · 94 across the 8 of their papers we have counts for
8 papers
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…
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…
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 Parametric Ordinal-Recursive Complexity of Post Embedding Problems
Prateek Karandikar, Sylvain Schmitz
Post Embedding Problems are a family of decision problems based on the interaction of a rational relation with the subword embedding ordering, and are used in the literature to 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…