Jaka jest złożoność stanu języka kopii?

Niech zostanie podana liczba . Rozważ następujący język . $n$ $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$

słowy, jest zbiorem ciągów kopii o długości . $L_n$ $2n$

Rozważmy następujący stan złożoność funkcji takie, że jest liczbą stanów w najmniejszym automatów ze stosem, który rozpoznaje . $s$ $s(n)$ $L_n$

Pytanie: Czy możesz formalnie udowodnić jakąkolwiek znaczącą dolną granicę dla ? $s(n)$

Moja hipoteza: . $s(n) = 2^{\Theta(n)}$

Znane górne ograniczenie: . $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$

Zasady:

(1) Alfabet stosu musi być binarny.

(2) Taśma wejściowa jest jednokierunkowa i nie może zatrzymać się na żadnym znaku wejściowym.

— Michael Wehar
źródło

Obecnie nie mam żadnej znaczącej dolnej granicy. Wydaje mi się, że możesz być w stanie udowodnić dolną granicę liczby zmiennych potrzebnych dla CFG, które rozpoznają język. Chociaż nie jestem tego całkowicie pewien.

— Michael Wehar,

Moją intuicją jest to, że kiedy popychasz znaki z taśmy wejściowej na stos, napotykasz problem. Jeśli chcesz później odzyskać te bity, musisz wyrzucić wszystkie bity, które naciskałeś nad nim. Innymi słowy, wydaje się, że stos ci nie pomaga, ponieważ im więcej do niego naciskasz, tym bardziej musisz później zapomnieć.

— Michael Wehar,

Uwaga: W przypadku DFA (automaty bez stosu) możesz udowodnić dolną granicę złożoności stanu wykładniczego.

— Michael Wehar,

Czy potrafisz wskazać rozsądną dolną granicę prostszego problemu ?

{0^{k} 1^{l} 0^{k} 1^{l}}

$\{0^k1^l0^k1^l\}$

— András Salamon,

Bardziej precyzyjną górną granicą wydaje się być stany.

(n + 3) 2^{n / 2}

$(n+3)2^{n/2}$

— András Salamon,

Technika opisana przez Yuvala:

Czy istnieje wielomianowy rozmiar CFG opisujący ten skończony język?

(możesz także przeczytać: Dolne granice wielkości CFG dla określonych języków skończonych )

pozwala bardzo łatwo pokazać wykładniczą dolną granicę dla CFG. Niech gramatyka w normalnej formie Chomsky'ego dla . Dla każdego słowa istnieje co najmniej jeden nieterminalny akceptujący podsłowie o mające długość od do . Niech będzie pozycją w której występuje to pod-słowo. Istnieją co najmniej bity wspólne dla wszystkich słów takie, że i . W rezultacie może być najwyżej $G$ $L_n$ $w\in \{0,1\}^n$ $A(w)$ $s(w)$ $ww$ $n/2$ $n$ $p(w)$ $ww$ $n/2$ $w,w'$ $A(w)=A(w')$ $p(w)=p(w')$ $2^{n/2}$ słowa, które mają takie same i . Dlatego istnieją co najmniej nieterminale. $A(w)$ $p(w)$ $2^{\Theta(n)}$

Co więcej, PDA można przekształcić w CFG w CNF o wielkości wielomianowej, więc daje to również związane ze złożonością stanu . $2^{\Theta(n)}$ $L_n$

— Joseph Stack
źródło

Wspaniale, jeszcze raz dziękuję! Widzę teraz i pomyślę o tym, aby potwierdzić. :)

— Michael Wehar,

Jeszcze raz: zmiana długości z na wprowadziła inny problem. Musiałem udoskonalić argument w sposób podobny do argumentu Yuvala (liczenie się pokrywa). Teraz wierzę, że to w końcu jest poprawne. Zredagowałem odpowiedź i usunąłem swoje komentarze

[n, 2 n]

$[n,2n]$

[n / 2, n]

$[n/2,n]$

— Joseph Stack

W przypadku, gdy pomaga to komukolwiek innemu: zwróć uwagę, że po wybraniu , może dać tylko jedno podmenu które zaczyna się na pozycji . To faktycznie pokazuje, że każda poprawna CNF-CFG dla tego języka musi mieć wiele nieterminali, z których każdy generuje jedno długie pod-słowo.

(A (w), p (w))

$(A(w),p(w))$

A (w)

$A(w)$

w w

$ww$

p (w)

$p(w)$

— András Salamon

Zobacz także Twierdzenie 7 w mojej pracy: cs.toronto.edu/~yuvalf/CFG-LB.pdf .

— Yuval Filmus

@YuvalFilmus Warto również zauważyć, że Andras spędził trochę czasu próbując dopasować górną i dolną granicę. Mój przyjaciel Pepe i ja zdefiniowaliśmy ogólną klasę skończonych języków i zastosowaliśmy do nich tę technikę. Jednak nigdy niczego nie napisaliśmy. Jeśli kiedykolwiek pojawią się jakieś problemy, chętnie będziemy współpracować. Dzięki jeszcze raz.

— Michael Wehar