On the index of Simon's congruence for piecewise testability

• We provide upper and lower bounds for Simon's index for piecewise testability.
• This index depends on the length of considered subwords and the alphabet size.
• The previously known bounds focused on fixed length of subwords.
• Our bounds are relevant when alphabet size is fixed and length of subwords vary.
• They give a growth rate that is exponential and not doubly exponential.

Simon's congruence, denoted by ∼n∼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 ∼n∼n is in 2Θ(nk−1log⁡n)2Θ(nk−1log⁡n).