Loughborough University
Browse

On the index of Simon's congruence for piecewise testability

Download (129.87 kB)
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

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

© Elsevier

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

DOI

ISSN

0020-0190

Publisher version

Language

  • en

Administrator link

Usage metrics

    Loughborough Publications

    Categories

    Keywords

    Combinatorics of wordsPiecewise testable languagesSubwords and subsequencesInformation and Computing Sciences not elsewhere classified

    Licence

    CC BY-NC-ND 4.0

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC