48 citations · 94 across the 8 of their papers we have counts for
Showing cs.FLShow all
2 papers · 1 filter
cs.FL2014★ 18 cited
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…
cs.FL2013★ 48 cited
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…