Kufleitner_1310.1278v5.pdf (129.87 kB)
Download fileOn the index of Simon's congruence for piecewise testability
journal contribution
posted 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θ).
Funding
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.
History
School
- Science
Department
- Computer Science