Prateek Karandikar - cp's OEIS frontend

User: Prateek Karandikar

Prateek Karandikar has authored 2 sequences.

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

3, 16, 152, 2326, 52132, 1602420, 64529264

Offset: 1

Prateek Karandikar and Philippe Schnoebelen, Oct 09 2013

Consider an alphabet with n letters, say {a_0, a_1, ... a_{n-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.

Define two words to be 2-equivalent if they have the same subsequences of length up to 2. The n-th term of this sequence is the number of equivalence classes of this equivalence relation, when the size of the alphabet is n.

			For n=1, with the alphabet {a_0}, representatives of the three equivalence classes are: empty word, a_0, a_0a_0.

Prateek Karandikar and Philippe Schnoebelen, On the index of Simon's congruence for piecewise testability arXiv:1310.1278 [cs.FL], 2013-2014.

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

Original entry on oeis.org

1, 4, 16, 68, 312, 1560, 8528, 50864, 329248, 2298592, 17203264, 137289920

Offset: 0

Prateek Karandikar and Philippe Schnoebelen, Oct 09 2013

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 n-equivalent if they have the same subsequences of length up to n. The n-th term of this sequence is the number of equivalence classes of this equivalence relation.

			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.

Prateek Karandikar and Philippe Schnoebelen, On the index of Simon's congruence for piecewise testability, arXiv:1310.1278 [cs.FL], 2013-2014.

cp's OEIS Frontend

User: Prateek Karandikar

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

Views

Author

Keywords

Comments

Examples

Links