21
$\begingroup$

For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite index and [SS83] asks what is the number of congruence classes. Has there been any progress on this question? I cannot find any recent paper mentioning it.

Write $k=\mid A\mid$ for the cardinal of $A$. Since two different words of length at most $n$ cannot be congruent, there must be at least $\mid A^{\leq n}\mid=k^n+k^{n-1}+\cdots+1=\frac{k^{n+1}-1}{k-1}$ congruence classes. And since each class is characterized by a subset of $A^{\leq n}$, there are less than $2^{\mid A^{\leq n}\mid}\leq 2^{k^{n+1}}$ congruence classes.

For $n=1$, $\sim_1$ means "same set of occurring letters" and obviously there are $2^k$ congruence classes. But observe that, for $n>1$, not all subsets of $A^{\leq n}$ are realizable sets of subwords. E.g., if $x$ has $aa$ and $bb$ as subwords of length $n=2$, it must also have $ab$ or $ba$ (at least one of them).

There is a very large gap between the obvious lower and upper bounds given above. Can we narrow it? The question I am interested in is for fixed $k$ and as a function of $n$, is the number of classes simply exponential or doubly exponential? (or something else?)

Added June 17th: Write $C_{n,k}$ for the number of classes. I did some computations for $k=3$, i.e., when $A=\{a,b,c\}$ has three letters: \[ C_{0,3}=1, \quad C_{1,3}=8, \quad C_{2,3}=152, \quad C_{3,3}=5312, \quad C_{4,3}=334202. \] This leaves me perplexed. Much bigger than $k^n$ but much smaller than $2^{k^n}$.

Added June 26th: For $k=2$, $C_{n,2}$ can be bounded by $2^{2n^2+1}$, hence is "simply" exponential. Indeed, when $A=\{a,b\}$, a shortest witness for a congruence class does not have $n+1$ consecutive $a$'s (or $b$'s) and does not alternate more than $2n$ times between $a$'s and $b$'s. Hence each congruence class has a witness of length $\leq 2n^2$.

References: [SS83] J. Sakarovitch and I. Simon's. "Subwords", chapter 6 in M. Lothaire's Combinatorics on words, 1983.

Acknowledgments: Jean-Éric Pin pointed me to the [SS83] ref for the open question.

$\endgroup$
  • $\begingroup$ I think this is still open. $\endgroup$ – Benjamin Steinberg Jun 11 '13 at 13:45
  • 1
    $\begingroup$ So anagrams in general are 1-related but not 2-related? Gerhard "Likes The Phrase Anagram Sheperd" Paseman, 2013.06.11 $\endgroup$ – Gerhard Paseman Jun 11 '13 at 22:55
  • 1
    $\begingroup$ I believe the original reference for this problem may be Simon, I. Piecewise testable events. In Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975) (Berlin, 1975), vol. 33 of Lecture Notes in Comput. Sci., Springer, pp. 214–222. $\endgroup$ – Vince Vatter Jun 20 '13 at 13:44
  • 2
    $\begingroup$ The bound given for $k=2$ is still very loose: if my calculations are correct, the sequence $C_{n,2}$ starts with $1,4,16,68,312,1560,\ldots$ $\endgroup$ – Ale De Luca Jun 26 '13 at 21:02
  • 2
    $\begingroup$ Thanks for the calculations. My $C_{n,2}$ values agree and go on with ..,1560,8528,50864,... so we can confirm one another's code. I agree that the upper bound is loose. However, my question is, for fixed $k$, whether $C_{n,k}$ is simply or doubly exponential in $n$. This is now answered for $k=2$. $\endgroup$ – phs Jun 26 '13 at 21:09
6
$\begingroup$

A bound is given in the paper

On the word problem for syntactic monoids of piecewise testable languages,
by K. Kátai-Urbán, P.P. Pach, G. Pluhár, A. Pongrácz and C. Szabó.

See Prop. 5.1: $\log C_{n,k}=\Theta(k^{(n+1)/2})$ if $n$ is odd, and $\log C_{n,k} = \Theta(k^{n/2} \log k)$, if $n$ is even.

$\endgroup$
  • $\begingroup$ Thanks for pointing to this recent paper! Very interesting. The way I see it, it does not exactly answer my question since it fixes $n$ and let $k$ vary. In particular, the multiplicative constants implicit in the $\Theta(..)$ notation of Prop. 5.1 are different for each value of $n$. $\endgroup$ – phs Jun 29 '13 at 10:13
4
$\begingroup$

I could generalize my earlier proof for the $k=2$ case and show that, for any fixed $k$, $C_{n,k}$ is in $2^{O(n^k)}$ hence simply exponential.

When some given $n$ is understood, we say that $x\in A^*$ is minimal if $x$ has minimal length inside its $\sim_n$-class. Since $\sim_n$ is a congruence, all factors of a minimal $x$ are themselves minimal.

For a fixed $k$-letter alphabet $A$, write $l_{n,k}$ for the length of the longest minimal word wrt $\sim_n$. Thus $C_{n,k}\leq k^{l_{n,k}+1}$ since every congruence class has a minimal representative.

A word $x\in A^*$ is rich if each letter of $A$ occurs at least once in $x$, otherwise $x$ is poor. A minimal poor word has length $\leq l_{n,k-1}$ since at least one letter is not used.

We decompose a word $x$ under the form $x=r_1 \cdots r_m\cdot x'$ where $r_1$ is the shortest rich prefix of $x$, $r_2$ is the shortest rich prefix of the rest, etc., until there only remains a poor suffix $x'$. E.g., assuming $k=3$, $x=bbaaabbccccaabbbaa$ is written $x=bbaaabbc\cdot cccaab \cdot bbaa$. Also, if $x$ is poor then $m=0$ and $x'=x$.

Assume now that $x$ is minimal. Then $\mid{x'}\mid\leq l_{n,k-1}$ since $x'$ is poor. Also, for any $i=1,\ldots,m$, $\mid{r_i}\mid\leq 1+l_{n,k-1}$, since $r_i$ minus its last letter is not yet rich. If now $m\geq n$ then $x$ already has all possible subwords (so $\mid{x}\mid=kn$ if $x$ is minimal). Otherwise $m<n$ and $\mid{x}\mid\leq n\cdot l_{n,k-1}+n-1$. We deduce $l_{n,k}\leq \max(kn,n\cdot l_{n,k-1}+n-1)$. Since $l_{n,1}=n$ we see that $l_{n,k}< n^k+n^{k-1}+\cdots+n+1$. Hence for fixed $k$, $C_{n,k}$ is in $2^{O(n^k)}$.

$\endgroup$
  • 1
    $\begingroup$ A more detailed analysis by P. Karandikar and myself is now available at arxiv: 1310.1278. It shows the $2^{O(n^k)}$ upper bound for $C_{n,k}$ and a new $2^{\Omega(n^{k-1})}$ lower bound. The comments we received here were a great help and motivation. Thanks to all. $\endgroup$ – phs Oct 7 '13 at 4:05
  • 1
    $\begingroup$ After one year, and with some outside help, we improved this to a "tight" $2^{\Theta(n^{k-1}\log n)}$ asymptotic value. See last version of arxiv: 1310.1278. $\endgroup$ – phs Oct 12 '14 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.