Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

EDITED TO ADD: This question is now essentially answered; please see this blog entry for more details. Thanks to everyone who posted comments and answers here.


ORIGINAL QUESTION

This is a hopefully smarter and better-informed version of a question I asked on MathOverflow. When I asked that question, I did not even know the name of the area of mathematics my problem was in. Now I am pretty sure it lies in Algorithmic Combinatorics on Partial Words. (Recent book on the subject here.)

I want to make a list of words on $l$ letters. Each word has length exactly $k$. The deal is, if $a \lozenge ^j b$ is in the list, where $\lozenge$ is a wildcard/don't-care symbol, then $a \lozenge ^j b$ can never appear again in the list. (The same holds true if $a=b$, or if $j=0$ and hence the prohibited subword is $ab$.)

Example where $k=4$ and $l=5$:

$abcd$
$bdce$
$dcba$ <-- prohibited because $dc$ appeared in the line above
$aeed$ <-- prohibited because $a \lozenge \lozenge d$ appeared on the first line

The literature on "avoidable partial words" that I have found has all been infinitary -- eventually some word pattern is unavoidable if the word size is large enough. I would like to find finitary versions of such theorems. So, question:

Given a partial word of form $a \lozenge^j b$ in an alphabet of $l$ letters, how many words of length $k$ avoid it, and can they be explicitly produced in polynomial time?

I don't expect the above question to be difficult, and, unless there is a subtlety I am missing, I could calculate it myself. The real reason I am posting on this site is because I need to know a lot more about the properties of such word lists for my application, so I am hoping someone can answer the followup question:

Has this been studied in generality? What are some papers that consider, not just whether a partial word is eventually unavoidable, but "how long it takes" before it becomes unavoidable?

Thanks.

share|improve this question
    
(1) I cannot understand the correspondence between your first question and the example stated before it. What is the input in your example? (2) In your first question, are you using k for two different purposes? –  Tsuyoshi Ito Aug 19 '11 at 15:44
    
Regarding (2), yes I made a mistake, now edited, thank you. –  Aaron Sterling Aug 19 '11 at 15:51
    
Regarding (1), I would like to know "how much room I have left" once a partial word appears. But yes, the real question is how to produce lists like the one that appears in the example (without the prohibited partial words). So the input would be the values of $k$ and $l$, and a desired number of words to produce in a list, all of which had the "avoidance of previously appearing partial words property." –  Aaron Sterling Aug 19 '11 at 15:53
2  
@Aaron, I don't know what your ultimate application is, but Davenport-Schinzel sequences (and generalizations) ask about the maximum length of a string that does not contain a particular repeating pattern. It's a related notion. –  Suresh Venkat Aug 19 '11 at 16:44
1  
Seth Pettie has been studying some very nifty generalizations to forbidden submatrices as well. –  Suresh Venkat Aug 19 '11 at 20:12

3 Answers 3

up vote 4 down vote accepted

Here's a special case: the number of binary words of length $k$ such that no two ones appear consecutively is $F(k+3)$, where $F(n)$ is the $n^{th}$ Fibonacci number (starting with $F(1)=1, F(2)=1$). Proof is via the Zeckendorf representation.

EDIT: We can extend this initial special case into the slightly larger special case of $a\lozenge^0a$. Consider strings of length $k$ over an alphabet of size $l+1$ such that the letter $a$ does not appear twice consecutively. Let $f(k)$ be the number of such strings (which we will call "valid"). We claim that: $$f(k) = l*f(k-1) + l*f(k-2)$$ $$ f(0) = 1, f(1) = l+1$$ The intuition is that we can construct a valid string of length $k$ by either: a) adjoining any of the $l$ letters that are not $a$ to a valid string of length $k-1$, or b) adjoining the letter $a$ and then any other letter but $a$ to a valid string of length $k-2$.

You can verify that the following is a closed form for the above recurrence: $$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$ where we understand ${{n}\choose{i}} = 0$ when $i>n$.

EDIT #2: Let's knock out one more case -- a $\lozenge^0 b, a \neq b$. We'll call strings over an $l$-element alphabet that do not contain the substring $ab$, "valid" and let $S_k$ denote the set of valid strings of length $k$. Further, let's define $T_k$ to be the subset of $S_k$ consisting of strings starting with $b$ and $U_k$ to be those not starting with $b$. Finally, let $f(k) = |S_k|$, $g(k) = |T_k|$, $h(k) = |U_k|$.

We observe that $g(0)=0, h(0)=1, f(0)=1$ and $g(1)=1, h(1)=l-1, f(1)=l$. Next, we infer the following recurrences: \begin{eqnarray} g(k+1) &=& f(k) \\ h(k+1) &=&(l-1)*h(k) + (l-2)*g(k) \end{eqnarray} The first comes from the fact that adding a $b$ to the start of any element of $S_k$ produces an element of $T_{k+1}$. The second comes from observing that we can construct an element of $U_{k+1}$ by adding any character but $b$ to the front of any element of $U_{k}$ or by adding any character but $a$ or $b$ to the front of any element in $T_k$.

Next, we rearrange the recurrence equations to obtain: \begin{eqnarray} f(k+1) &=& g(k+1) + h(k+1) \\ &=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\ &=& f(k) + (l-1)*f(k) - g(k) \\ &=& l*f(k) - f(k-1) \end{eqnarray}

We can get a rather opaque closed-form solution to this recurrence by mucking around a bit with generating function stuff or, if we're lazy, heading straight to Wolfram Alpha. However, with a little bit of googling and poking around in OEIS, we find that we actually have: $$f(k) = U_k(l/2)$$ where $U_k$ is the $k^{th}$ Chebyshev polynomial of the second kind (!).

share|improve this answer
    
That's very interesting, thank you. –  Aaron Sterling Aug 21 '11 at 16:49

A completely different approach for the first question reuses the answers to the recent question on generating words in a regular language: it suffices to apply these algorithms for length $k$ on the regular language $\Sigma^\ast a\Sigma^j b\Sigma^\ast$ where $\Sigma$ is the alphabet.

share|improve this answer
    
Thanks. I was wondering if there might be a connection, and your answer here gave me the push I needed to look at the papers referenced there, and one of them definitely solves a piece of one of the problems I am considering. –  Aaron Sterling Aug 22 '11 at 17:28

Updated: this answer is incorrect:

assuming $j$ is fixed, we can count the number of ways a pattern $a\lozenge^j b$ can be matched: the first $a$ symbol can be matched at some position $1\leq i\leq k-j-1$, and we have $l^{i-1}$ possibilities before that point, $l^j$ between $a$ and $b$, and $l^{k-j-i-1}$ for the remainder of the string, thus a total of $$\sum_{i=1}^{k-j-1}l^{i-1}\cdot l^{j}\cdot l^{k-j-i-1}=(k-j-1)l^{k-2}$$ cases. As noted by Tsuyoshi Ito in the comments, this count is not the number of different words matching $a\lozenge^j b$ since a single word could match the same pattern in different ways. For instance $aa$ is matched three times in $aaaa$, $ab$ two times in $abab$, and $a\lozenge b$ two times in $aabb$. We can try to count the number of ways of matching patterns several times and exhibit an "inclusion-exclusion" expression, but the ways pattern might overlap makes this too long.


For the first question, under the understanding that $j$ is not fixed, i.e. that we want to avoid embedding the word $ab$:

  • either $a$ the first symbol never appears, which accounts for $(l-1)^k$ possible words,
  • or $a$ appears first in some position $1\leq i\leq k$, then we cannot use $b$ in the remainder of the word: there are $(l-1)^{i-1}$ choices for the factor up to $a$, and $(l-1)^{k-i}$ choices for the remainder, giving in total $\sum_{i=1}^k(l-1)^{i-1}\cdot(l-1)^{k-i}=k(l-1)^{k-1}$ possible words. Whether $a=b$ is irrelevant.

For the second question, I don't have much to suggest; there is a relation with word embeddings, but the results I know about bad sequences for Higman's Lemma do not immediately apply.

share|improve this answer
    
Thanks very much, Sylvain, though I don't think that's quite right. We can use $b$ later in the word if $a$ appears. We just can't use $b$ if there are exactly $j$ letters in between $a$ and $b$, if $a \lozenge ^j b$ appeared earlier. Perhaps I am misunderstanding your argument though. –  Aaron Sterling Aug 19 '11 at 20:57
    
Sorry, I wasn't sure whether $j$ was fixed or not. I've edited the answer with fixed $j$ as well. –  Sylvain Aug 19 '11 at 21:04
1  
I do not think that the fixed-j case is correct. For example, if k=4 and j=1, the word aabb is subtracted twice. I haven’t read the non-fixed-j case. –  Tsuyoshi Ito Aug 20 '11 at 13:09
    
@Tsuyoshi Ito: you're right, there is no unique match in that case. –  Sylvain Aug 20 '11 at 15:39
    
Please mark an incorrect answer as such. –  Tsuyoshi Ito Aug 20 '11 at 17:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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