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.

Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.

We call a $k$-covering of $L_n$ is a set $C$ with elements are $k$-length words, $k\le n$, such that every word from $L_n$ have at least a continuous part that is a word in $C$.

My question is what is the possible minimum size of a $k$-covering for $L_n$ (depends on $k, m, n$), and how many k-coverings for $L_n$ at all? The algorithm problem is also interesting about finding a $k$-covering with minimum size.

Another type of "$k$-covering" is also not trivial, with the same questions:

Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible n-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.

We call a $k$-covering of $L_n$ is a subset $C$ of $L_n$, $k\le n$, such that every word from $L_n$ have at least a $k$-continuous part that is also a continuous part of some word in $C$, or we can say every $n$-length word $k$-match with some word in $C$.

Note: For more convenient in discussion, I call the first one "type I", and second one "type II" $k$-covering.

share|improve this question
    
if i understand correctly: if C is the set of all singletons $a_i$, $C$ is a covering for any $L_n$ right? –  Jorge Fernández Jul 24 '12 at 20:30
    
yes. this is the simplest case for 1-covering. –  Minh Nguyen Jul 24 '12 at 20:40
    
When $m=2$, I think the problem maybe gives meaning in code theory. –  Minh Nguyen Jul 24 '12 at 20:56
    
Have you already determined the minimal type I $2$-covering? It's not too hard. –  Erick Wong Jul 24 '12 at 23:12
1  
@ChuckFernández Sorry, had an error in my previous argument. The case of type I $2$-coverings amounts to asking "What is the largest directed graph on $m$ vertices that doesn't contain a walk of length $n-1$?" (Look at the complement of $C$). If $n > m$ this is equivalent to a directed acyclic graph, which is well-known to have at most $m(m-1)/2$ edges, so $|C| \ge m(m+1)/2$ and this is tight. –  Erick Wong Jul 25 '12 at 0:22

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.