6
$\begingroup$

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.

  • 0
    if i understand correctly: if C is the set of all singletons $a_i$, $C$ is a covering for any $L_n$ right?2012-07-24
  • 0
    yes. this is the simplest case for 1-covering.2012-07-24
  • 0
    When $m=2$, I think the problem maybe gives meaning in code theory.2012-07-24
  • 0
    Have you already determined the minimal type I $2$-covering? It's not too hard.2012-07-24
  • 0
    @MinhNguyen For $k,m$ fixed, I believe the minimum $k$-covering size for $L_n$ is eventually constant for $n$ sufficiently large. Are you interested in this large $n$ regime (which seems quite tractable), or the smaller values of $n$?2012-07-25
  • 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.2012-07-25
  • 0
    What can you say about 2-covering for second type problem?2012-07-26

0 Answers 0