Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us fix an alphabet $\Sigma=\{0,1,2,\dots,n-1\}$ for a given $n$ and consider words over $\Sigma$, i.e. elements of $\Sigma^*$.

Consider the following 5 words:

$$000\\001\\002\\010\\100$$

They satisfy the property that for every two indices $1\le i_1,i_2\le 3$, if we take the subwords obtained from the letters in the indices $i_1, i_2$, we will end up with two identical subwords. For example, if $i_1=1,i_2=3$ then both $000$ and $010$ give the subword $00$.

What I want is this: to find a value $t$ such that for all the possible sets of 5 distinct words of equal ($\ge t$) size, there exists some choice of $t$ indices which gives rise to distinct subwords for all the words. My example shows that $t=2$ will not work.

I only need a solution for the case $n=5$ right now, but I'm also interested in the most general case, where we need to find a $t$ that is good not only for sets of size $5$ but for sets of size $r$ for some integer $r$. Hence, I'm actually asking about computing/bounding a function $t(n,r)$ which depends on both the size of the alphabet and the cardinality of the set of words.

share|improve this question
    
Maybe I'm not understanding your question, but it seems $t$ has to be the length of your strings, regardless of $n$ and $r$. You could always have $001, 000, 100$ as part of your set (with more zeros if your strings are longer) and you have to check all the bits to tell them apart. –  Ross Millikan Oct 23 '12 at 14:03
    
Indeed, I had a big phrasing error. Fixed to "here exists some choice of t indices which gives rise to distinct subwords for all the words". Thanks! –  Gadi A Oct 23 '12 at 14:28

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.