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

59

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.

Gęś kanadyjska
źródło
16
Pierwszym otwartym problemem, jaki przyszedł mi do głowy, jest to, czy domysł Czarnego jest prawdziwy. en.wikipedia.org/wiki/Synchronizing_word and liafa.jussieu.fr/~jep/Problemes/Cerny.html Poniższy post na blogu może być również dla Ciebie interesujący: rjlipton.wordpress.com/2009/08/17/…
Abuzer Yakaryilmaz
1
Czy liczą się otwarte problemy dotyczące NFA i wyrażeń regularnych?
Hsien-Chih Chang 張顯 之
1
@ Hsien-Chih: bądźmy jak najbardziej restrykcyjni w interpretacji pytania. Zakładałem, że nie ma już otwartych problemów, ale odpowiedzi pokazują, że to nieprawda.
Kanadyjska gęś
1
DFA i wyrażenia regularne są równoważne. NFA i DFA są równoważne pod względem mocy ekspresyjnej, chociaż NFA może mieć znacznie mniej stanów niż odpowiadający mu DFA.
chepner
6
@chepner Chociaż DFA, NFA i wyrażenia regularne są równoważne pod względem siły ekspresji, to wcale nie oznacza, że ​​wiedza o jednym z nich oznacza znajomość wszystkiego o drugim. Na przykład wiedza na temat minimalizacji DFA nie mówi bezpośrednio, jak zminimalizować NFA - co w rzeczywistości jest dość trudnym problemem !
Daniel Wagner

Odpowiedzi:

55

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?uv|u|=|v|=nuv

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(n2/5(logn)3/5)Ω(logn)

Aby zobaczyć ankietę, zobacz to .

Hsien-Chih Chang 張顯 之
źródło
12
W moim ostatnim przemówieniu na BCTCS 2014 na Uniwersytecie Loughborough oferuję 100 GBP za wszelkie nietrywialne postępy w tym problemie. Aha, są też wymienione inne otwarte problemy! Zobacz cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .
Jeffrey Shallit
1
Zaakceptuję to, ponieważ był to pierwszy, ale wszystkie są świetnymi odpowiedziami. Dzięki wszystkim i nie przestawaj!
Kanadyjska gęś
Teraz w Wikipedii jako en.wikipedia.org/wiki/Separating_words_problem
David Eppstein
40

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.)22n+110+1

Jeffrey Shallit
źródło
istnieją różne inne przypuszczenia w teorii liczb, które odnoszą się do okresów np Erdos rozbieżności problemu & tieing niektórych preparatów DFA wydaje się możliwe w innych przypadkach też ewentualny program badawczy dla kogoś ...
vzn
Czy rozumiem poprawnie, że gdybyśmy mieli algorytm dla tego problemu, rozwiązałoby to również problem Sierpińskiego i problem Riesela? ( en.wikipedia.org/wiki/Sierpinski_number , en.wikipedia.org/wiki/Riesel_number )
sdcvvc
Tak, sdcvvc, tak jest.
Jeffrey Shallit
38

n(n1)2O(n3)

David Eppstein
źródło
Przepraszamy, Abuzer Yakaryilmaz, nie zauważyłem twojego komentarza przed opublikowaniem go jako odpowiedzi. Ale wierzę, że zasługuje na odpowiedź, a nie tylko komentarz ...
David Eppstein
2
Żaden problem :) Myślę, że drugi otwarty problem, który połączyłem, również wygląda całkiem interesująco.
Abuzer Yakaryilmaz
7
(n1)2n3/6
@SashoNikolov Praktyczne może być zresetowanie systemu do znanego stanu bez konieczności jego obserwowania (na przykład satelity) przy użyciu najmniejszej liczby działań.
Denis,
Tak, po raz pierwszy dowiedziałem się o tym problemie podczas pracy Natarajana nad projektowaniem komponentów linii montażowych, które mechanicznie wymuszają na nich elementy w określonych orientacjach geometrycznych. Krótsze sekwencje resetowania (w automacie reprezentującym potencjalne etapy reorientacji) = krótsze linie montażowe.
David Eppstein,
20

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

2n2n

Problem z liczbą magiczną

αn2nLnα

αα

13

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.

Hermann Gruber
źródło
7
To świetny problem! Ale kto wymyślił termin „magiczna liczba”, powinien zostać zastrzelony.
Jeffrey Shallit
19

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

D1D2xD1D2x

o(n2)

O(nδ)δ

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! :)

Michael Wehar
źródło
cześć MW, cieszę się, że zauważyłeś to pytanie. niedawno cytowany cię na tej drugiej kwestii ponownego rozdzielania P / L . jak niedawno udowodniłeś, powyższe pytanie (górne granice złożoności rozwiązania problemu braku pustki wielu DFA) jest ściśle związane z (głównym otwartym problemem) oddzielania P / NL.
vzn
Dziękuję Ci bardzo! Kim jesteś? Poszedłem na twój blog i rozejrzałem się, ale nie mogłem tego rozgryźć.
Michael Wehar
1
D1D2Ω(n2)
12

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.

Lew Reyzin
źródło
12

LLLlLlLlO(n2)

Saeed
źródło
5

n

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

n

mikero
źródło
To jest naprawdę fajne. Zdarzyło mi się myśleć o tym innego dnia i nie wiedziałem, że inni nad tym pracowali. Dzięki za udostępnienie. :)
Michael Wehar
4
Dlaczego uważasz, że istnieje zamknięta formuła? Myślę, że to bardzo mało prawdopodobne.
domotorp
Zobacz także to pytanie dotyczące tego, co wiadomo na temat tego problemu: Jaka liczba języków jest akceptowana przez DFA o rozmiarze n
Hermann Gruber,
2

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

nΣ={0,1}DFA(n)n|DFA(n)|=n2n2n

x,yΣKn(x,y)DFA(n) xy

Kn(x,y)Kn(x,y)poly(n,|x|,|y|)

To pytanie ma wpływ na uczenie maszynowe .

Aryeh
źródło
Jaki jest obecny stan złożoności problemu?
Ryan
1
Jeremiah Blocki miał pewne częściowe wyniki; jest to stan wiedzy o ile mi wiadomo: cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf
Aryeh
-3

(„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).

nxnxn

DFAnDFADFAnDFAnDFA, jest także RL (i DFA).

Σ

nDFAnΣ

Σ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.

vzn
źródło
2
Myślę, że mylisz pojęcia „nierozstrzygalny” i „otwarty”.
Lew Reyzin
jak przyznaje, jest to co najmniej niezwykły i / lub niekonwencjonalny pogląd, ale nie jestem jedynym, który go poparł. patrz np. ten cytat Michela w tym artykule Problemy w teorii liczb z zajętej konkurencji bobrów . również podobne sentymenty wyrażone w słynnej teorii liczb otwartych przypuszczają na temat prostego problemu, którego nierozstrzygalność jest nieznana . patrz również automatyczne twierdzenie o dowodzeniu vs nierozstrzygalność
vzn
DFAnΣn{1nDFAnΣ}
DFA