On the index of Simon's congruence for piecewise testability

2013/10/31 by Prateek Karandikar, Manfred Kufleitner, Philippe Schnoebelen · 1 citation
Computer Science · Mathematics · #cs.FL #cs.DM #math.CO

paper · pdf · doi:10.1016/j.ipl.2014.11.008

published as Information Processing Letters, 115(4):515-519, 2015

arxiv created 2014/09/22 · arxiv updated 2016/07/07

Abstract

Simon's congruence, denoted ∼_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 log n).

Cited by

• Decomposition of Automata recognizing Ideals

Related

• Testing Simon's congruence
• m-Nearly k-Universal Words -- Investigating Simon Congruence
• On the piecewise complexity of words
• On the piecewise complexity of words and periodic words
• α-β-Factorization and the Binary Case of Simon's Congruence