

A228950


The index of Simon's piecewise testability congruence, for words of length n over a 2letter alphabet.


0



1, 4, 16, 68, 312, 1560, 8528, 50864, 329248, 2298592, 17203264, 137289920
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Consider an alphabet with two letters, say {0,1}. For two words v and w over this alphabet, we say v embeds in w, or v is a subsequence of w, if v can be obtained from w by erasing some (occurrences of) letters.
For a natural number n, define two words to be nequivalent if they have the same subsequences of length up to n. The nth term of this sequence is the number of equivalence classes of this equivalence relation.


LINKS

Table of n, a(n) for n=0..11.
Prateek Karandikar and Philippe Schnoebelen, On the index of Simon's congruence for piecewise testability, arXiv:1310.1278 [cs.FL], 20132014.


EXAMPLE

For n=1, here are representatives of each of the four equivalence classes (taking the alphabet to be {0,1}) : empty word, 0, 1, 01.


CROSSREFS

Sequence in context: A006319 A202020 A059606 * A231297 A231358 A000303
Adjacent sequences: A228947 A228948 A228949 * A228951 A228952 A228953


KEYWORD

nonn,more


AUTHOR

Prateek Karandikar and Philippe Schnoebelen, Oct 09 2013


STATUS

approved



