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…