두 글자가 같지 않도록 Σ 위에있는 모든 k 문자 문자열 로 구성된 언어 L k – d i s t i n c t를 고려하십시오 .Lk−distinctkΣ

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

이 언어는 유한하며 규칙적입니다. 특히 | Σ | = n|Σ|=n 이면 | L k − d i s t i n c t | = ( nk ) k!|Lk−distinct|=(nk)k!.

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

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

• 구성 할 수있는 가장 작은 NFA는 4 k ( 1 + o ( 1 ) ) ⋅ p o l y l o g ( n )4k(1+o(1))⋅polylog(n) 상태입니다.

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

하자 L ⊆ Σ ∗L⊆Σ∗ 일반 언어합니다. i = j 인 경우에만 x_i \ cdot w_j \ in L 이되도록 엔n 쌍 P = { ( x i , w i ) ∣ 1 ≤ i ≤ n }P={(xi,wi)∣1≤i≤n} 있다고 가정 합니다. 그런 다음 L을 수락하는 NFA는 적어도 n 개의 상태를 갖습니다.xi⋅wj∈Lxi⋅wj∈Li=ji=j

• 또 다른 (사소한) 하한은 loglog(nk)(nk) . 이는 언어에 대한 가장 작은 DFA 크기의 로그입니다.

I는 (에만 고정 부분을 수용하는 NFA 쌍이에 관심 0<ϵ<10<ϵ<1 )의 Lk−distinctLk−distinct , 오토 마톤의 크기보다 작은 경우 ϵ⋅4k(1+o(1))⋅polylog(n)ϵ⋅4k(1+o(1))⋅polylog(n) .

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

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

편집 2 :

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

L(r,k)−distinct:={w:wL(r,k)−distinct:={w:w 포함 kk 구별 된 심볼들을 더 심볼 이상 나타나지 rr 시간 }} .

(예 : L(1,k)−distinct=Lk−distinctL(1,k)−distinct=Lk−distinct ).

주석의 구성과 유사한 구조는 대해 크기의 오토 마톤을 제공합니다. .O(ek⋅2k⋅log(1+r)⋅poly(n))O(ek⋅2k⋅log(1+r)⋅poly(n))L(r,k)−distinctL(r,k)−distinct

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

답변