On the index of Simon's congruence for piecewise testability
journal contributionposted on 2018-02-23, 09:20 authored by P. Karandikar, Manfred Kufleitner, P. Schnoebelen
© 2014 Elsevier B.V. Simon's congruence, denoted by ∼ 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 is in 2 Θ (n k-1 lognθ).
This work was partially supported by Tata Consultancy Services. M.K. was supported by ANR grant 11-BS02-001-01. P.S. was supported by DFG grant DI 435/5-2.
- Computer Science