18
$\begingroup$

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:

$$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

This language is finite and therefore regular. Specifically, if $\left|\Sigma\right|=n$, then $\left|L_{k-distinct}\right| = \binom{n}{k} k!$.

What is the smallest non-deterministic finite automaton that accepts this language?

I currently have the following loose upper and lower bounds:

  • The smallest NFA I can construct has $4^{k(1+o(1))}\cdot polylog(n)$ states.

  • The following lemma implies a lower bound of $2^k$ states:

Let $L ⊆ Σ^*$ be a regular language. Suppose there are $n$ pairs $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ such that $x_i\cdot w_j \in L$ if and only if $i=j$. Then any NFA accepting L has at least n states.

  • Another (trivial) lower bound is $log$$n\choose k$, which is the log of the size of the smallest DFA for the language.

I am also interested in NFAs that accept only a fixed fraction ($0<\epsilon<1$) of $L_{k-distinct}$, if the size of the automaton is smaller than $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$.

Edit: I've just started a bounty that had a mistake in the text.

I meant we may assume $k=polylog(n)$ while I wrote $k=O(log(n))$.

Edit2:

The bounty is going to end soon, so if anyone is interested in what is perhaps an easier way to earn it, consider the following language:

$L_{(r,k)-distinct} :=\{w : w$ contains $k$ distinct symbols and no symbol appear more than $r$ times$\}$.

(i.e. $L_{(1,k)-distinct} = L_{k-distinct}$).

A similar construction as the one in the comments gives $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ sized automaton for $L_{(r,k)-distinct}$.

Can this be improved? What's the best lower bound we can show for this language?

Improve this question
$\endgroup$
21
  • 3
    $\begingroup$ Can you describe your upper-bound NFA? $\endgroup$
    – mjqxxxx
    Commented Jan 6, 2014 at 19:32
  • 1
    $\begingroup$ In the lemma that gives the lower bound, in fact it is enough to require that $x_iw_i\in L$ and for every $i,j$ either $x_iw_j\notin L$ or $x_jw_i\notin L$. The proof that such families cannot have a cardinality bigger than $2^k$ was proved by Tuza: link.springer.com/article/10.1007%2FBF01788531 $\endgroup$
    – domotorp
    Commented Mar 22, 2014 at 20:09
  • 4
    $\begingroup$ The lower bound gives $(2-o(1))^k$ just counting the number of states that the NFA can be in after exactly $k/2$ steps. I don't think that I am aware of any proof method that gives significantly better bounds for the total size than what can be obtained than by just looking at what happens after $t$ steps, for some $t$. But here, for every $t$ there is an NFA that can be in only one of $(2+o(1))^k$ states after exactly $t$ states. $\endgroup$
    – Noam
    Commented Mar 23, 2014 at 5:51
  • 3
    $\begingroup$ Proof (of my previous claim): The hardest case is $t=k/2$; choose $2^k \cdot poly(k, \log n)$ different random subsets $S_i$ (of the $n$ alphabet symbols) of size exactly $t$ each and construct an NFA that has a state for each $i$ with some path leading to it iff the first $t$ symbols are all different and are contained in $S_i$, and has an accepting path from it iff the following $k-t$ symbols are all different and are contained in the complement of $S_i$. A counting argument will show that whp (over the random choice of the $S_i$'s) this NFA will indeed accept all of the desired language. $\endgroup$
    – Noam
    Commented Mar 23, 2014 at 5:59
  • 3
    $\begingroup$ In the previous construction, the simplest way to build the NFA will have a state for each possible prefix of length $j < t$ and for each possible suffix of length $j > k-t$. Instead, the prefix part and suffix part of the NFA can be built recursively using the same randomized construction (but now only within $S_i$ and its complement, respectively) and this would give a $(4+o(1))^k$ total size. $\endgroup$
    – Noam
    Commented Mar 23, 2014 at 6:13

2 Answers 2

Reset to default
2
+50
$\begingroup$

This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $S_A$ and the states from which an accepting state can be reached after reading the elements of $B$ (in any order) by $T_B$. We need that $S_A\cap T_B\ne \emptyset$ if and only if $A\cap B=\emptyset$. This already gives a lower bound for the required number of states and I think it could give something non-trivial.

This problem essentially asks for a lower bound on the number of the vertices of a hypergraph whose line graph is (partially) known. Similar problems were studied e.g., by Bollobas and there are several known proof methods that can be useful.

Update 2014.03.24: In fact if the above hypergraph can be realized on $s$ vertices, then we also get a non-deterministic communication complexity protocol of length $\log s$ for set disjointness with inputs sets of size $a$ and $b$ (in fact the two problems are equivalent). The bottleneck is of course when $a=b=k/2$, for this I could only find the following in Eyal and Noam's book: $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ proved by the standard probabilistic argument. Unfortunately I could not (yet) find good enough lower bounds on this problem but assuming the above is sharp, it would give a lower bound $\Omega(2^k\log n)$ unifying the two lower bounds you have mentioned.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thanks @domotorp for your answer. This seems a lot like the proof of the lemma I've used for the lower bound in the original question, but without specifying the actual $x_i$'s and $y_i$'s, and thus not a countable bound. Your comment on the question above suggests that the $2^k$ bound can't be improved by that method, do you think this could do better? $\endgroup$
    – R B
    Commented Mar 23, 2014 at 17:32
  • 4
    $\begingroup$ The whole point of my comment above was that these techniques can not give a lower bound above $(2+o(1))^k$. This is really what makes this problem interesting to me. $\endgroup$
    – Noam
    Commented Mar 23, 2014 at 17:43
  • 1
    $\begingroup$ @Noam: Let k=2, a=b=1. Already then we get a $\log n$ lower bound as every $S_A$ has to be different. $\endgroup$
    – domotorp
    Commented Mar 23, 2014 at 17:46
  • 1
    $\begingroup$ @domotorp: The $o(1)$ hides a $O(k\log n)$ factor: Here is the analysis for the worst case where $a=b=k/2$: Start with a fixed $A$ and $B$ and pick at random a subset $S$ of the $n$ letters then we have $Pr[A \subseteq S \:and\: B \subseteq S^c]=2^{-k}$. Now pick $r2^k$ such sets at random then the probability that for at least one of them this happens is $1-exp(-r)$. If we choose $r = O(\log {n \choose k}) = O(k \log n)$ then we get that whp this is so for ALL disjoint sets $A$ and $B$ (of size $k/2$). The total number of such $S$'s in this construction is $O(2^k k \log n)$. $\endgroup$
    – Noam
    Commented Mar 23, 2014 at 19:07
  • 2
    $\begingroup$ @Noam: I am sorry but I have never seen a $\log n$ hidden in an $o(1)$, especially as the problem is also interesting imho for $k<<\log n$. But you are right that R B asked about $k=polylog n$. $\endgroup$
    – domotorp
    Commented Mar 23, 2014 at 22:26
0
$\begingroup$

Some work in progress:

I'm trying to prove a lower bound of $4^k$. Here is a question that I'm pretty sure would give such a lower bound: find the minimum $t$ such that there exists a function $f:\{S \subseteq [n], |S|=k/2 \} \rightarrow \{0,1\}^t$ that preserves disjointness, i.e. that $S_1 \cap S_2 = \emptyset$ iff $f(S_1) \cap f(S_2) = \emptyset$. I'm pretty sure a lower bound of $t \ge 2k$ would almost immediately imply a lower bound of $2^{2k}=4k$ for our problem. $f(S)$ roughly corresponds to the set of nodes the NFA can get to after reading the first $k/2$ symbols of the input, when the set of these $k/2$ symbols is $S$.

I think the solution to this question might already be known, either in the communication complexity literature (especially in papers dealing with the disjointness problem; maybe some matrix rank arguments will help), or in literature about encodings (e.g. like this).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ My comments above show that this approach cannot beat $(2+o(1))^n$ $\endgroup$
    – Noam
    Commented Mar 27, 2014 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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