Czy ciągła dwuznaczność może zmniejszyć złożoność stanu zwykłych języków?

Mówimy, że NFA jest stale niejednoznaczny, jeśli istnieje tak że każde słowo jest akceptowane przez lub (dokładnie) ścieżek. $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Jeśli automat jest stale niejednoznaczny dla , wówczas nazywa się Jednoznacznym FA (UFA). $M$ $k=1$ $M$

Niech będzie zwykłym językiem. $L$

Czy jakiś stale dwuznaczny automat dla być mniejszy niż najmniejszy UFA, który akceptuje ? Ile może to być mniejsze? $M_c$ $L$ $L$

Czy automat całkowicie niejednoznaczny może być wykładniczo mniejszy niż najmniejszy CFA dla tego samego języka?

Wiadomo, że istnieją całkowicie niejednoznaczne automaty (istnieje , takie, że każde słowo jest akceptowane przez maksymalnie ścieżek), które są wykładniczo mniejsze niż najmniejsze UFA dla tego samego języka, ale nie widziałem nic o stałej dwuznaczności. $k$ $k$

Oto pokrewne pytanie , które zamieściłem tutaj kilka miesięcy temu.

EDYTOWAĆ:

Odpowiedź Domotorp pokazuje, że jest wielomianowo redukowalny do , ale nie odnosi się do pytania, czy możemy uzyskać tę redukcję przestrzeni wielomianowej przez . $CFA$ $UFA$ $CFA$

Tak więc nowe pytanie brzmi: o ile mniejsze (liniowo / kwadratowe / itp.) Można porównać do minimalnego ? dla tego samego języka? $CFA$ $UFA$

czy -transitions jest dozwolone?

ϵ

$\epsilon$

Denis

Być może może to być pomocne: w Kupke, O oddzielaniu stałej od wielomianowej niejednoznaczności automatów skończonych, przedstawiona jest następująca hierarchia: Nie sprawdziłem powiązanego papieru, ponieważ jest za paywall.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Dzięki @MarzioDeBiasi, ale niestety to nie pomaga (miałem również nadzieję, kiedy zobaczyłem prezentację). Używają innej notacji niż ta, której używam (i widziałem w różnych artykułach). Ich „stała dwuznaczność” jest tym, co nazwałem skończoną dwuznacznością, więc związek między ich Cafą a UFA był mi już znany. Ponieważ moja aplikacja liczy rozwiązania problemów NPC, mój język jest zawsze skończony i dlatego każde słowo jest akceptowane przez ścieżki

, które nazywają „stałymi”.

O (1)

$O(1)$

Zastanawiam się, czy moja definicja pomaga zmniejszyć złożoność stanu, ponieważ mam CFA, który jest wykładniczo mniejszy niż najmniejszy UFA, jaki potrafię zbudować, i zastanawiałem się, czy to możliwe, że nie ma małego UFA dla tego języka.

@Denis, tak, ale czy pomogłoby to zmniejszyć złożoność stanu? Zakładam, że dzięki takim ruchom można zmniejszyć liczbę krawędzi.

Odpowiedzi:

I twierdzą, że jeśli z jakiegoś języka jest CFA zz stanach i lub przyjmując ścieżki dla każdego słowa, to nie jest UFA z stanach. Podstawową ideą jest to, że stany UFA są (uporządkowanymi) c-krotkami stanów CFA i akceptuje wtedy i tylko wtedy, gdy wszystkie stany c akceptują. Oczywiście musimy również upewnić się, że były to rzeczywiście różne obliczenia i że nie liczymy wszystkich permutacje, więc dla nich musimy jakieś dodatkowe bitów przechowywania. $s$ $0$ $c$ $C_ss^c$ $c!$ $C_s$

Nieco bardziej szczegółowy opis podstawowych idei: if jest stanem UFA, to ma przejście od niego (czytanie trochę się ) do stanu wtedy i tylko wtedy, gdy CFA ma przejście (czytanie litery ) z na dla każdego . Stan $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ akceptuje wtedy i tylko wtedy, gdy akceptuje dla każdego . Oczywiście stanem początkowym UFA jest gdzie jest stanem początkowym CFA. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

Problem z powyższego jest taka, że symulowane przebiegi CFA może być taka sama. Więc dodajemy dodatkowe informacje, zakodowane, powiedzmy, na wykresie na wierzchołkach, który ma krawędź między wierzchołkiem a wierzchołkiem jeśli podczas dotychczasowego przebiegu przynajmniej raz mieliśmy to . $c$ $c$ $i$ $j$ $c_i\ne c_j$

Teraz nadal mamy problem, że policzyliśmy wszystko razy z powodu możliwych permutacji. Możemy temu zaradzić, wymagając, aby jeśli ty i ty stany były do tej pory takie same, aw następnym kroku będą się różnić, to w następnym kroku ty stan powinien mieć większy indeks. $c!$ $i$ $j$ $i$

domotorp
źródło

Dziękuję za odpowiedź @domotorp. Niestety nie mogę powiedzieć, że to rozumiem. Czy możesz podać więcej szczegółów (np. Jak zakodowany byłby dowód pierwszeństwa?). Dzięki !

W każdym razie zdałem sobie sprawę, że istnieje również UFA dla tego języka, więc zapomnij o nim. A co z pozostałą częścią mojej odpowiedzi?

domotorp

Nie jestem pewien, czy podążam. Jeśli

jest CFA z

, nie oznacza to, że dla każdego słowa

mogą istnieć tylko

ścieżki , tylko że tylko

z nich zakończy się stanem akceptującym. Jakie byłyby stany UFA? Czy możesz spróbować go sformalizować?

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Proszę bardzo, mam nadzieję, że teraz jest jasne.

domotorp