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

18

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 - d i s t i n c tLkdistinct k kΣΣ

L k - d i s t i n c t : = { w = σ 1 σ 2 . . . σ ki [ k ] : σ iΣ  and  j i : σ jσ i }  

Lkdistinct:={w=σ1σ2...σki[k]:σiΣ  and  ji:σjσi}

Ten język jest skończony i dlatego regularny. W szczególności, jeśli , to \ left | L_ {k-odrębny} \ right | = \ binom {n} {k} k! .| Σ | = n |Σ|=n| L k - d i s t i n c t | = ( nk ) k!|Lkdistinct|=(nk)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 ) )p o l y l o g ( n )4k(1+o(1))polylog(n) .

  • Poniższy lemat implikuje dolną granicę stanów 2 tys2k :

Niech L ΣLΣ będzie zwykłym językiem. Załóżmy, że istnieje nn par P = { ( x i , w i ) 1 i n }P={(xi,wi)1in} takich, że x iw jLxiwjL wtedy i tylko wtedy, gdy i = ji=j . Wtedy każdy NFA akceptujący L ma co najmniej n stanów.

  • Kolejną (trywialną) dolną granicą jest l o g log( nk )(nk) , 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 < ϵ < 10<ϵ<1 ) L k - d i s t i n c tLkdistinct , jeśli rozmiar automatu jest mniejszy niż ϵ 4 k ( 1 + o ( 1 ) )p o l y l o g ( n )ϵ4k(1+o(1))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 = p o l y l o g ( n )k=polylog(n) podczas gdy ja napisałem k = O ( l o g ( n ) )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 ) - d i s t i n c t : = { w : wL(r,k)distinct:={w:w zawiera kk różnych symboli i żaden symbol nie pojawia się więcej niż rr razy }} .

(tj. L(1,k)distinct=LkdistinctL(1,k)distinct=Lkdistinct ).

Podobna konstrukcja jak w komentarzach daje automat wielkości O(ek2klog(1+r)poly(n))O(ek2klog(1+r)poly(n)) dla L(r,k)distinctL(r,k)distinct .

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

RB
źródło
2
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 ( ( 2 e ) k2 O ( l o g ( k ) )l o g ( n ) ) ( n , k ) H h : [ n ] [ k ] [ n ] k h H k 2 k L k - d i s t i n cO((2e)k2O(log(k))log(n))(n,k)Hh:[n][k][n]khHk2ktLkdistinct
RB
4
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 k / 2 t t t ( 2 + o ( 1 ) ) k t(2o(1))kk/2ttt(2+o(1))kt
Noam
3
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 wyboremt = k / 2 2 kp o l y ( k , log n ) S i n t i t S i k - t S i S it=k/22kpoly(k,logn)SintitSiktSiSis) ten NFA rzeczywiście zaakceptuje cały pożądany język.
Noam
3
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<tj<tj>ktj>ktSiSi(4+o(1))k(4+o(1))k
Noam

Odpowiedzi:

2

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 wtedyaaaa[n][n]AAb=kab=ka[n][n]BBAASASABBTBTBSATBSATBAB=AB=. 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ęsslogslogsa b a = b = k / 2 N 1 ( D I S J a ) log ( 2 k log e ( naba=b=k/2a ) )Ω(2klogn)N1(DISJa)log(2kloge(na))Ω(2klogn) ujednolicając dwie dolne granice, o których wspomniałeś.

domotorp
źródło
1
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? x i y i 2 kxiyi2k
RB
3
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. log n SlognSA
domotorp
1
@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ścio ( 1 ) O ( k log n ) a = b = k / 2 A B S n P r [ A Sa n dB S c ] = 2 - k r 2 k 1 - e x p ( - r ) r = O ( log ( nk ) )=O(klogn)ABk/2SO(2kklogn)). Całkowita liczba takich w tej konstrukcji wynosi .
Noam
2
@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 = P O L y l O g N
domotorp
0

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 tych4 k t f : { S [ n ] , | S | = k / 2 } { 0 , 1 } t S 1S 2 = f ( S 1 ) f ( S 2 ) = t 2 k 2 2 k = 4 k f ( S )k / 2 k / 2symboli .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
2
Moje powyższe komentarze pokazują, że to podejście nie może pokonać(2+o(1))n
Noam