On the index of Simon's congruence for piecewise testability
arXiv:1310.1278 · doi:10.1016/j.ipl.2014.11.008
Abstract
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^{k-1} log n)}.
Cited by in corpus (7)
- Counting the number of non-zero coefficients in rows of generalized Pascal triangles
- The height of piecewise-testable languages and the complexity of the logic of subwords
- Efficiently Testing Simon's Congruence
- Piecewise Testable Languages and Nondeterministic Automata
- On -piecewise testability (preliminary report)
- Existential Definability over the Subword Ordering
- On the Height of Towers of Subsequences and Prefixes