두 글자가 같지 않도록 Σ 위에있는 모든 k 문자 문자열 로 구성된 언어 L k – d i s t i n c t를 고려하십시오 .$L_{k-distinct}$$k$$\Sigma$

L k – d i s t i n c t : = { w = σ 1 σ 2 . . . σ k ∣ ∀ i ∈ [ k ] : σ i ∈ Σ  및  ∀ j ≠ i : σ j ≠ σ i }  

$$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 \}$$

이 언어는 유한하며 규칙적입니다. 특히 $\left|\Sigma\right|=n$ 이면 $\left|L_{k-distinct}\right| = \binom{n}{k} k!$.

이 언어를 받아들이는 가장 작은 비 결정적 유한 오토 마톤은 무엇입니까?

현재 다음과 같은 느슨한 상한과 하한이 있습니다.

• 구성 할 수있는 가장 작은 NFA는 $4^{k(1+o(1))}\cdot polylog(n)$ 상태입니다.

• 다음의 정리는 $2^k$ 상태의 하한을 의미합니다 .

하자 $L ⊆ Σ^*$ 일반 언어합니다. i = j 인 경우에만 x_i \ cdot w_j \ in L 이되도록 $n$ 쌍 $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ 있다고 가정 합니다. 그런 다음 L을 수락하는 NFA는 적어도 n 개의 상태를 갖습니다.$x_i\cdot w_j \in L$$i=j$

• 또 다른 (사소한) 하한은 $log$$n\choose k$ . 이는 언어에 대한 가장 작은 DFA 크기의 로그입니다.

I는 (에만 고정 부분을 수용하는 NFA 쌍이에 관심 $0<\epsilon<1$ )의 $L_{k-distinct}$ , 오토 마톤의 크기보다 작은 경우 $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$ .

편집 : 나는 텍스트에 실수가있는 현상금을 시작했습니다.

k = O (log (n))을 쓰는 동안 k = polylog (n) 이라고 가정 할 수 있었습니다 .$k=polylog(n)$$k=O(log(n))$

편집 2 :

바운티가 곧 종료 될 것이므로 누구나 쉽게 얻을 수있는 방법에 관심이 있다면 다음 언어를 고려하십시오.

$L_{(r,k)-distinct} :=\{w : w$ 포함 $k$ 구별 된 심볼들을 더 심볼 이상 나타나지 $r$ 시간 $\}$ .

(예 : $L_{(1,k)-distinct} = L_{k-distinct}$ ).

주석의 구성과 유사한 구조는 대해 크기의 오토 마톤을 제공합니다. .$O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$$L_{(r,k)-distinct}$

이것을 개선 할 수 있습니까? 이 언어에 가장 적합한 하한은 무엇입니까?

답변