Ograniczenia wielkości najmniejszego NFA dla L_k-odrębne

Rozważmy język składający się ze wszystkich ciągów -lettera nad tak aby żadne dwie litery nie były równe: $L_{k-distinct}$ $k$ $\Sigma$

L k - d i s t i n c t : = {w = σ 1 σ 2 . . . σ k ∣ \forall i \in [k] : σ i \in Σ and \forall j \neq i : σ j \neq σ 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 \}$

Ten język jest skończony i dlatego regularny. W szczególności, jeśli , to . $\left|\Sigma\right|=n$ $\left|L_{k-distinct}\right| = \binom{n}{k} k!$

Jaki jest najmniejszy niedeterministyczny automat skończony, który akceptuje ten język?

Obecnie mam następujące luźne górne i dolne granice:

Najmniejszy NFA, jaki mogę zbudować, ma $4^{k(1+o(1))}\cdot polylog(n)$ .
Poniższy lemat implikuje dolną granicę stanów $2^k$ :

Niech $L ⊆ Σ^*$ będzie zwykłym językiem. Załóżmy, że istnieje $n$ par $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ takich, że $x_i\cdot w_j \in L$ wtedy i tylko wtedy, gdy $i=j$ . Wtedy każdy NFA akceptujący L ma co najmniej n stanów.

Kolejną (trywialną) dolną granicą jest $log$ $n\choose k$ , który jest logiem wielkości najmniejszego DFA dla języka.

Interesują mnie również NFA, które akceptują tylko stały ułamek ( $0<\epsilon<1$ ) $L_{k-distinct}$ , jeśli rozmiar automatu jest mniejszy niż $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$ .

Edycja: Właśnie rozpocząłem nagrodę, która zawierała błąd w tekście.

Miałem na myśli, że możemy założyć $k=polylog(n)$ podczas gdy ja napisałem $k=O(log(n))$ .

Edycja2:

Nagroda wkrótce się skończy, więc jeśli ktoś jest zainteresowany łatwiejszym sposobem jej zdobycia, rozważ następujący język:

$L_{(r,k)-distinct} :=\{w : w$ zawiera $k$ różnych symboli i żaden symbol nie pojawia się więcej niż $r$ razy $\}$ .

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

Podobna konstrukcja jak w komentarzach daje automat wielkości $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ dla $L_{(r,k)-distinct}$ .

Czy można to poprawić? Jaka jest najlepsza dolna granica dla tego języka?

— RB
źródło

Czy możesz opisać swój górny limit NFA?

— mjqxxxx,

Nie mogę jeszcze o tym pisać, ponieważ wciąż nad tym pracujemy i nie ukończyłem dowodu. Zamiast tego opiszę o wiele prostszy automat wielkości : weź idealną rodzinę mieszającą . Każdy taki skrót jest funkcją . Oznacza to, że dla każdego podzbioru wielkości co najwyżej istnieje funkcja , która odwzorowuje każdy element tego podzestawu na inną liczbę. Po haszowaniu powstały alfabet ma liter, dlatego autumaton o rozmiarze może zaakceptować język .

O((2e)k∗2O(log(k))∗log(n)) $O((2e)^k * 2^{O(log(k))} * log(n))$

(n,k) $(n,k)$

H $H$

h:[n]→[k] $h: [n] \to [k]$

[n] $[n]$

k $k$

h∈H $h\in H$

k $k$

2k $2^k$

Lk−distinct $L_{k-distinct}$

— RB

Dolna granica daje tylko zliczając liczbę stanów, w których NFA może znajdować się po dokładnie krokach. Nie sądzę, że znam jakąkolwiek metodę dowodu, która daje znacznie lepsze granice dla całkowitego rozmiaru niż to, co można uzyskać, niż po prostu patrząc na to, co dzieje się po krokach, dla niektórych . Ale tutaj, dla każdego istnieje NFA, który może znajdować się tylko w jednym z stanów po dokładnie stanach.

(2−o(1))k $(2-o(1))^k$

k/2 $k/2$

t $t$

(2+o(1))k $(2+o(1))^k$

t $t$

— Noam

Dowód (z mojego poprzedniego twierdzenia): najtrudniejszy przypadek to ; wybierz różne losowe podzbiory (z symboli alfabetu) o wielkości dokładnie dokładnie każdy i NFA, który ma stan dla każdego z pewną ścieżką prowadzącą do niego w pierwszym symbole są różne i są zawarte w , i ma od niego ścieżkę akceptującą, jeżeli następujące symbole są różne i są zawarte w dopełnieniu . Argument liczący pokaże, że whp (ponad losowym wyborem

t=k/2 $t=k/2$

2k⋅poly(k,logn) $2^k \cdot poly(k, \log n)$

Si $S_i$

n $n$

t $t$

i $i$

t $t$

Si $S_i$

k−t $k-t$

Si $S_i$

Si $S_i$ s) ten NFA rzeczywiście zaakceptuje cały pożądany język.

— Noam

W poprzedniej konstrukcji najprostszym sposobem na zbudowanie NFA będzie stan dla każdego możliwego prefiksu długości i dla każdego możliwego sufiksu długości . Zamiast tego część przedrostka i część przyrostka NFA można budować rekurencyjnie przy użyciu tej samej losowej konstrukcji (ale teraz tylko odpowiednio w i jej dopełnieniu), a to dałoby całkowity rozmiar .

j<t $j < t$

j>k−t $j > k-t$

Si $S_i$

(4+o(1))k $(4+o(1))^k$

— Noam

Odpowiedzi:

To nie jest odpowiedź, ale metoda, która moim zdaniem pozostawiłaby lepszą dolną granicę. Przetnijmy problem po litery są odczytywane. Oznacza rodzinę zestawy elementem od oraz rodzina zestawów elementem za . Oznacz stany, które można osiągnąć po odczytaniu elementów (w dowolnej kolejności) przez oraz stany, z których stan akceptacyjny można osiągnąć po odczytaniu elementów (w dowolnej kolejności) przez . Potrzebujemy tego wtedy i tylko wtedy $a$ $a$ $[n]$ $\mathcal A$ $b=k-a$ $[n]$ $\mathcal B$ $A$ $S_A$ $B$ $T_B$ $S_A\cap T_B\ne \emptyset$ $A\cap B=\emptyset$ . To już stanowi dolną granicę dla wymaganej liczby stanów i myślę, że może dać coś nietrywialnego.

Ten problem zasadniczo wymaga dolnej granicy liczby wierzchołków hipergraphu, którego wykres liniowy jest (częściowo) znany. Podobne problemy były badane np. Przez Bollobasa i istnieje kilka znanych metod dowodowych, które mogą być przydatne.

Aktualizacja 2014.03.24: W rzeczywistości, jeśli powyższy hipergraph można zrealizować na wierzchołkach , wówczas otrzymujemy również niedeterministyczny protokół złożoności komunikacji o długości dla zestawu rozłączności z zestawami danych wejściowych o wielkości i (w rzeczywistości dwa problemy są równoważne). Wąskim gardłem jest oczywiście, gdy , w tym celu mogłem znaleźć tylko w książce i Noama: potwierdzony przez standardowy argument probabilistyczny. Niestety nie mogłem (jeszcze) znaleźć wystarczająco dobrych dolnych granic tego problemu, ale zakładając, że powyższe jest ostre, dałoby to dolną granicę $s$ $\log s$ $a$ $b$ $a=b=k/2$ $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ $\Omega(2^k\log n)$ ujednolicając dwie dolne granice, o których wspomniałeś.

— domotorp
źródło

Dzięki @domotorp za odpowiedź. To wydaje się bardzo podobne do dowodu lematu, którego użyłem dla dolnej granicy w pierwotnym pytaniu, ale bez określenia rzeczywistych i , a zatem nie do policzenia. Twój komentarz do powyższego pytania sugeruje, że tą metodą nie można poprawić granicy Czy uważasz, że można to zrobić lepiej?

xi $x_i$

yi $y_i$

2k $2^k$

— RB

Chodzi mi o to, że powyższe techniki nie mogą dać dolnej granicy powyżej . To właśnie sprawia, że ten problem jest dla mnie interesujący.

(2+o(1))k $(2+o(1))^k$

— Noam

@Nam: Niech k = 2, a = b = 1. Już wtedy otrzymujemy dolną granicę, ponieważ każdy musi być inny.

logn $\log n$

SA $S_A$

— domotorp

@domotorp: ukrywa współczynnik : Oto analiza najgorszego przypadku, w którym : Zacznij od stałej i i losowo wybierz podzbiór spośród liter mamy . Teraz wybierz losowo takie zestawy , a następnie prawdopodobieństwo, że tak się stanie przynajmniej dla jednego z nich, to . Jeśli wybierzemy , otrzymamy to, że tak jest w przypadku WSZYSTKICH rozłącznych zestawów i (o wielkości

$o(1)$

$O(k\log n)$

$a=b=k/2$

$A$

$B$

$S$

$n$

$Pr[A \subseteq S \:and\: B \subseteq S^c]=2^{-k}$

$r2^k$

$1-exp(-r)$

$r = O(\log {n \choose k}) = O(k \log n)$

$A$

$B$

$k/2$ ). Całkowita liczba takich w tej konstrukcji wynosi .

$S$

$O(2^k k \log n)$

— Noam

@Noam: Przykro mi, ale nigdy nie widziałem ukrytego w , szczególnie, że problem jest również interesujący imho dla . Ale masz rację, że RB zapytał o .

$\log n$

$o(1)$

$k<<\log n$

$k=polylog n$

— domotorp

Trwają prace:

Próbuję udowodnić dolną granicę . Oto pytanie, które jestem pewien, że dałoby taką dolną granicę: znajdź minimum tak aby istniała funkcja który zachowuje rozłączność, tzn. Że iff . Jestem prawie pewien, że dolna granica prawie natychmiast oznaczałaby dolną granicę dla naszego problemu. grubsza odpowiada zestawowi węzłów, do których NFA może się dostać po odczytaniu pierwszych symboli wejścia, gdy zestaw tych $4^k$ $t$ $f:\{S \subseteq [n], |S|=k/2 \} \rightarrow \{0,1\}^t$ $S_1 \cap S_2 = \emptyset$ $f(S_1) \cap f(S_2) = \emptyset$ $t \ge 2k$ $2^{2k}=4k$ $f(S)$ $k/2$ $k/2$ symboli . $S$

Myślę, że rozwiązanie tego pytania może być już znane, albo w literaturze dotyczącej złożoności komunikacji (szczególnie w artykułach dotyczących problemu rozłączności; być może pomocne będą niektóre argumenty rang matrycowych) lub w literaturze na temat kodowania (np. Jak ta ).

— pierożek Mobiusa
źródło

Moje powyższe komentarze pokazują, że to podejście nie może pokonać

$(2+o(1))^n$

— Noam