On the index of Simon's congruence for piecewise testability

Karandikar, P.; Kufleitner, Manfred; Schnoebelen, P.

Kufleitner_1310.1278v5.pdf (129.87 kB)

On the index of Simon's congruence for piecewise testability

journal contribution

posted on 23.02.2018, 09:20 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

Published in

Information Processing Letters

Volume

115

Issue

4

Pages

515 - 519

Citation

KARANDIKAR, P., KUFLEITNER, M. and SCHNOEBELEN, P., 2015. On the index of Simon's congruence for piecewise testability. Information Processing Letters, 115(4), pp. 515-519.

Publisher

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2015

Notes

This paper was accepted for publication in the journal Information Processing Letters and the definitive published version is available at https://doi.org/10.1016/j.ipl.2014.11.008