48 citations · 94 across the 8 of their papers we have counts for
6 papers · 1 filter
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…
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…