Czy pozostały jakieś otwarte problemy związane z DFA?

Po przestudiowaniu deterministycznych automatów skończonych (DFA) w undergrad poczułem, że są one bardzo dobrze rozumiane. Moje pytanie brzmi, czy jest coś, czego wciąż nie rozumiemy. Nie mam na myśli uogólnień DFA, ale oryginalne niezmodyfikowane DFA, które badamy w studiach licencjackich.

To jest niejasne pytanie, ale mam nadzieję, że masz pomysł. Chcę zrozumieć, czy uczciwie jest powiedzieć, że całkowicie rozumiemy DFA. Naprawdę mam na myśli pytania, które są nieodłącznie związane z DFA, a nie problemy sztucznie stworzone, aby wyglądały jak problem z DFA. Podam przykład takiego problemu. Niech L będzie pustym językiem, jeśli P = NP, a niektóre ustalone nieregularne języki, jeśli P nie jest NP. Czy L może zostać zaakceptowany przez DFA? To pytanie dotyczy DFA, ale nie dotyczy ich w duchu. Mam nadzieję, że mój punkt widzenia jest jasny i nie otrzymuję pedantycznych odpowiedzi od ludzi.

Krótko mówiąc, to jest sprawiedliwe powiedzieć

Zasadniczo całkowicie rozumiemy DFA.

Przykro mi, jeśli okaże się, że jest to ogromny obszar badań, o którym nie wiedziałem i właśnie obraziłem całą społeczność ludzi.

Oto jeden problem opisany w książce „Drugi kurs języków formalnych i teorii automatów” autorstwa Shallita.

Niech i v będą dwoma odrębnymi słowami z | u | = | v | = n . Jaki jest rozmiar najmniejszego DFA, który akceptuje u, ale odrzuca v lub vice versa?$u$$v$$|u|=|v|=n$$u$$v$

Robson, w swojej pracy " oddzielające pasy ze małych automatach " w 1989 okazał się górnej granicy . Najbardziej znana dolna granica w Ω ( log n ) .$O(n^{2/5}(\log n)^{3/5})$$\Omega(\log n)$

Aby zobaczyć ankietę, zobacz to .

Oto bardzo prosty problem decyzyjny dotyczący DFA. Biorąc pod uwagę DFA M, czy M akceptuje reprezentację base-2 co najmniej jednej liczby pierwszej?

Obecnie nie wiemy nawet, czy ten problem można rozwiązać rekurencyjnie.

Jeśli jest on rekurencyjnie rozwiązywalny i mamy do tego algorytm, moglibyśmy rozwiązać długotrwały otwarty problem dotyczący tego, czy istnieją jakieś liczby pierwsze Fermata (liczby pierwsze w postaci ) większe niż największe znane, 65537. (Ponieważ każda liczba pierwsza z reprezentacją base-2 postaci 1 0 + 1 musi być liczbą pierwszą Fermata.)$2^{2^n} + 1$$1 0^+ 1$

$n$$(n-1)^2$$O(n^3)$

Chciałbym zwrócić uwagę na kolejny problem badawczy, który dotyczy interakcji bardzo podstawowych pojęć na temat DFA.

$2^n$$2^n$

Problem z liczbą magiczną

$\alpha$$n$$2^n$$L_n$$\alpha$

$\alpha$$\alpha$

$1$$3$

Galina Jirásková. Liczby magiczne i alfabet trójskładnikowy. W: 13. międzynarodowa konferencja nt. Rozwoju teorii języka (DLT 2009), tom 5583 Wykładów z informatyki, strony 300–311.

Tytuł: Brak pustki na skrzyżowaniu dla dwóch DFA

$D_1$$D_2$$x$$D_1$$D_2$$x$

$o(n^2)$

$O(n^{\delta})$$\delta$

Wyjaśnienie: Zdecydowanie o pustce przecięcia zwykłych języków w czasie subkwadratowym

Może ci się to przydać: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Miłego dnia! :)

Oto otwarty problem związany z DFA i teorią uczenia maszynowego: czy jednolicie losowe (losowe przejścia i zachowania akceptowania / odrzucania) DFA można poznać w modelu PAC?

Uwaga: uważamy, że arbitralne DFA nie są możliwe do nauczenia b / c wyników twardości kryptograficznej . W przypadku losowego DFA mamy tylko dolne granice SQ , które nie są tak silne.

$L$$L$$L$$l$$L$$l$$L$$l$$O(n^2)$

$n$

Wydaje mi się, że powinna istnieć formuła zamknięta, ale żadna nie jest znana. Niektóre asymptotyczne granice są znane:

$n$

Oto pytanie związane z DFA, które już tu byłam, i o ile wiem, wciąż jest otwarte:

$n$$\Sigma=\{0,1\}$$DFA(n)$$n$$|DFA(n)| = n^{2n}2^n$

$x,y\in\Sigma^*$$K_n(x,y)$$DFA(n)$ $x$$y$

$K_n(x,y)$$K_n(x,y)$$poly(n,|x|,|y|)$

To pytanie ma wpływ na uczenie maszynowe .

(„myślenie nieszablonowe” ...) jest to nieco wymyślony problem z udziałem DFA (nie widziałem, aby badano go gdzie indziej), ale przejawia się w TCS, że nawet wiele pozornie „prostych” obiektów obliczeniowych (takich jak DFA) może mieć złożone właściwości , także aspekt / temat zawarty w twierdzeniu Ricesa. (pod pewnymi względami ostateczną „złożonością” jest „nierozstrzygalność”, czyli kompletność Turinga).

$n$$x$$n$$x↑n$

$DFA_n$$DFA'$$DFA'$$n$$DFA_n$$DFA'$, jest także RL (i DFA).

$\Sigma$

$n$$DFA_n ≠ \Sigma*$

$\Sigma*$$n$

teraz, aby powiązać to bardziej z pytaniem, chociaż nie jest to powszechnie zauważane (przez niektórych uważane za trywialne), wiele otwartych problemów w TCS / matematyce jest ściśle związanych z nierozstrzygalnością w tym, biorąc pod uwagę wyrocznię dotyczącą problemu zatrzymania, mogą one być „ rozwiązany".

dlatego, w pewnym sensie, łącząc to wszystko za pomocą tego podstawowego problemu dotyczącego DFA, który jest nierozstrzygalny, zawsze będą otwarte problemy dotyczące DFA, ponieważ zawsze będą „otwarte” problemy dotyczące DFA (takie jak ten) równoważne nierozstrzygalnym problemom . w rzeczywistości wykorzystując twierdzenie Ricesa w odwrotnej kolejności, ponieważ ta konstrukcja robi to w pewien sposób, w zasadzie dowolną stosunkowo „prostą”, ale nietrywialną właściwość obliczeniową w TCS można wykorzystać do skonstruowania nierozstrzygalnych problemów.

[1] Problemy ze słowami wymagające czasu wykładniczego / Stockmeyer & Meyer

[2] Meyer, AR i L. Stockmeyer. Problem równoważności wyrażeń regularnych z kwadratem wymaga przestrzeni wykładniczej. 13. sympozjum IEEE na temat teorii przełączania i automatyki, październik 1972 r., S. 125–129.

[3] Wprowadzenie do języków, automatów i obliczeń / Hopcroft / Ullman.