107 citations · 401 across the 20 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.LO2015★ 10 cited
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…
cs.LO2015★ 5 cited
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…