On the index of Simon's congruence for piecewise testability

Manfred Kufleitner; Philippe Schnoebelen; Prateek Karandikar

arxiv: 1310.1278 · v5 · pith:MZ4M2BXYnew · submitted 2013-10-03 · 💻 cs.FL · cs.DM· math.CO

On the index of Simon's congruence for piecewise testability

Prateek Karandikar , Manfred Kufleitner , Philippe Schnoebelen This is my paper

classification 💻 cs.FL cs.DMmath.CO

keywords congruencesimonwordsalphabetdenotedhavingindexk-letter

0 comments

read the original abstract

Simon's congruence, denoted \sim_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 \sim_n is in 2^{\Theta(n^{k-1} log n)}.

This paper has not been read by Pith yet.

On the index of Simon's congruence for piecewise testability

discussion (0)