Gibt es noch offene Probleme mit DFAs?

59

Nachdem ich deterministische Finite-State-Automaten (DFA) im Grundstudium studiert hatte, fühlte ich mich sehr gut verstanden. Meine Frage ist, ob es etwas gibt, das wir noch nicht verstehen. Ich meine nicht Verallgemeinerungen von DFAs, sondern die ursprünglichen, nicht modifizierten DFAs, die wir in der Grundausbildung studieren.

Dies ist eine vage Frage, aber ich hoffe, dass Sie auf die Idee kommen. Ich möchte verstehen, ob es fair ist zu sagen, dass wir DFAs vollständig verstehen. Ich meine also wirklich Fragen, die sich inhärent auf DFAs beziehen, und keine Probleme, die künstlich wie ein Problem mit DFAs aussehen. Lassen Sie mich ein Beispiel für ein solches Problem geben. Sei L die leere Sprache, wenn P = NP und eine feste nicht reguläre Sprache, wenn P nicht NP ist. Kann L von einem DFA akzeptiert werden? Bei dieser Frage geht es um DFAs, aber nicht um sie im Geiste. Ich hoffe mein Standpunkt ist klar und ich bekomme keine pedantischen Antworten von Leuten.

Kurz gesagt ist es fair zu sagen

Wir verstehen DFAs im Wesentlichen vollständig.

Es tut mir leid, wenn sich herausstellt, dass dies ein riesiges Forschungsgebiet ist, von dem ich nichts wusste und das ich gerade eine ganze Gemeinschaft von Menschen beleidigt habe.

soft-question open-problem dfa Kanadische Gans
quelle

16

Das erste offene Problem, das mir in den Sinn kam, war, ob die Vermutung von Černý wahr ist. en.wikipedia.org/wiki/Synchronizing_word und liafa.jussieu.fr/~jep/Problemes/Cerny.html Der folgende Blog-Beitrag könnte auch für Sie interessant sein: rjlipton.wordpress.com/2009/08/17/…

Abuzer Yakaryilmaz

1

Zählen offene Probleme mit NFAs und regulären Ausdrücken?

Hsien-Chih Chang 張顯張顯

1

@ Hsien-Chih: Lassen Sie uns die Frage so restriktiv wie möglich interpretieren. Ich war davon ausgegangen, dass es keine offenen Probleme mehr gibt, aber die Antworten zeigen, dass dies nicht stimmt.

Kanadische Gans

1

DFAs und reguläre Ausdrücke sind gleichwertig. NFAs und DFAs sind in ihrer Ausdruckskraft gleichwertig, obwohl ein NFA möglicherweise weit weniger Zustände aufweist als sein entsprechender DFA.

Chepner

6

@chepner Obwohl DFAs, NFAs und Regexen in ihrer Ausdruckskraft gleichwertig sind, bedeutet dies keineswegs, dass alles über das eine zu wissen bedeutet, alles über das andere zu wissen. Wenn Sie beispielsweise wissen, wie Sie einen DFA minimieren, erfahren Sie nicht direkt, wie Sie einen NFA minimieren - was in der Tat ein ziemlich schwieriges Problem ist !

Daniel Wagner

55

Hier ist ein Problem beschrieben in dem Buch "Ein zweiter Kurs in formalen Sprachen und Automatentheorie" von Shallit.

Sei und zwei verschiedene Wörter mit . Was ist die Größe des kleinsten DFA , die akzeptiert lehnt aber , oder umgekehrt? $u$ $v$ $|u|=|v|=n$ $u$ $v$

Robson, in seinem Vortrag " Die Trennung Saiten mit kleinen Automaten " im Jahr 1989 erwies sich als eine obere Schranke . Die bekannteste Untergrenze in . $O(n^{2/5}(\log n)^{3/5})$ $\Omega(\log n)$

Eine Übersicht finden Sie hier .

Hsien-Chih Chang 張顯張顯
quelle

12

In meinem letzten Vortrag auf der BCTCS 2014 an der Loughborough University biete ich 100 GBP für jeden nicht trivialen Fortschritt in Bezug auf dieses Problem an. Oh, und es gibt auch noch andere offene Probleme! Siehe cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .

Jeffrey Shallit

1

Ich werde das akzeptieren, da es das erste war, aber es sind alles großartige Antworten. Danke an alle und macht weiter so!

Kanadische Gans

Jetzt in Wikipedia als en.wikipedia.org/wiki/Separating_words_problem

David Eppstein

40

Hier ist ein sehr einfaches Entscheidungsproblem für DFAs. Akzeptiert M bei gegebenem DFA M die Basis-2-Darstellung von mindestens einer Primzahl?

Derzeit wissen wir nicht einmal, ob dieses Problem rekursiv lösbar ist.

Wenn es rekursiv lösbar ist und wir einen Algorithmus dafür hatten, könnten wir das seit langem offene Problem lösen, ob es Fermat - Primzahlen (Primzahlen der Form ) gibt, die größer sind als die größte bekannte, 65537. (Weil Jede Primzahl mit Basis-2-Darstellung der Form muss eine Fermat-Primzahl sein.) $2^{2^n} + 1$ $1 0^+ 1$

Jeffrey Shallit
quelle

es gibt verschiedene andere Vermutungen in der Zahlentheorie, die sich auf Perioden beziehen, z. B. Erdos-Diskrepanzprobleme und die Einbindung einiger in DFA-Formulierungen scheint auch in anderen Fällen möglich zu sein, ein mögliches Forschungsprogramm für jemanden ...

vzn

Verstehe ich es richtig, dass wenn wir einen Algorithmus für dieses Problem hätten, dies auch Sierpinskis Problem und das Riesel-Problem lösen würde? ( en.wikipedia.org/wiki/Sierpinski_number , en.wikipedia.org/wiki/Riesel_number )

sdcvvc

Ja, sdcvvc, das ist der Fall.

Jeffrey Shallit

38

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

David Eppstein
quelle

Entschuldigung, Abuzer Yakaryilmaz, hat Ihren Kommentar nicht bemerkt, bevor er als Antwort veröffentlicht wurde. Aber ich glaube, es verdient eine Antwort und nicht nur einen Kommentar ...

David Eppstein

2

Kein Problem :) Ich finde das zweite offene Problem, das ich verlinkt habe, auch recht interessant.

Abuzer Yakaryilmaz

7

Ich weiß, dass dies eine berühmte Frage ist, aber gibt es eine kurze Erklärung, warum es eine wichtige ist? Was würden wir lernen, wenn die Schranke wirklich ist?

(n - 1)^{2}

$(n-1)^2$

n^{3} / 6

$n^3/6$

@SashoNikolov Es kann von praktischem Interesse sein, ein System mit der geringsten Anzahl von Aktionen in einen bekannten Zustand zurückzusetzen, ohne es beobachten zu müssen (z. B. ein Satellit).

Denis

Ja, ich habe dieses Problem zum ersten Mal durch die Arbeit von Natarajan an der Konstruktion von Komponenten von Montagelinien erfahren, die die Teile mechanisch dazu zwingen, sich in bestimmten geometrischen Ausrichtungen zu befinden. Kürzere Rücksetzsequenzen (in einem Automaten, der mögliche Umorientierungsschritte darstellt) = kürzere Montagelinien.

David Eppstein

20

Ich möchte auf ein weiteres Forschungsproblem hinweisen, das das Zusammenspiel sehr grundlegender Konzepte zu DFAs betrifft.

$2^n$ $2^n$

Problem mit magischen Zahlen

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

$\alpha$ $\alpha$

$1$ $3$

Galina Jirásková. Magische Zahlen und ternäres Alphabet. In: 13. Internationale Konferenz über Entwicklungen in der Sprachtheorie (DLT 2009), Band 5583, Lecture Notes in Computer Science, Seiten 300–311.

Hermann Gruber
quelle

7

Das ist ein großes Problem! Aber wer auch immer den Begriff "magische Zahl" erfunden hat, sollte erschossen werden.

Jeffrey Shallit

19

Titel: Schnittpunkt-Nicht-Leerheit für zwei DFAs

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

Offenes Problem: Können wir die Nicht-Leerheit der Kreuzung für zwei DFAs in lösen? $o(n^2)$

Wenn wir dieses Problem in lösen könnten $O(n^{\delta})$ $\delta$

Erklärung: Entscheidung über die Leere der Überschneidung regulärer Sprachen in subquadratischer Zeit

Dies könnte hilfreich sein: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Ich wünsche ihnen einen wunderbaren Tag! :)

Michael Wehar
quelle

hi mw froh, dass du diese frage bemerkt hast. Ich habe Sie kürzlich zu dieser anderen Frage bezüglich der Trennung von Gewinn- und Verlustrechnung zitiert . Wie Sie kürzlich bewiesen haben, hängt die obige Frage (obere Schranken der Komplexität der Lösung der Nicht-Leerheit mehrerer DFAs im Schnitt) eng mit dem (offenen Hauptproblem der) Trennung von P / NL zusammen.

vzn

Vielen Dank! Wer bist du vzn? Ich ging zu Ihrem Blog und sah mich um, konnte es aber nicht herausfinden.

Michael Wehar

1

D_{1}

$D_1$

D_{2}

$D_2$

Ω (n^{2})

$\Omega(n^2)$

12

Hier ist ein offenes Problem in Bezug auf DFA und Theorie des maschinellen Lernens: Sind DFAs im PAC-Modell einheitlich zufällig lernbar (zufällige Übergänge und Akzeptanz- / Zurückweisungsverhalten)?

Hinweis: Wir glauben, dass willkürliche DFAs aufgrund der Ergebnisse der kryptografischen Härte nicht lernbar sind . Für zufällige DFA haben wir nur SQ-Untergrenzen , die nicht so stark sind.

Lev Reyzin
quelle

12

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

Saeed
quelle

5

$n$

Es scheint mir, dass eine geschlossene Formel existieren sollte, aber keine ist bekannt. Einige asymptotische Grenzen sind bekannt:

$n$

mikero
quelle

Das ist wirklich cool. Ich habe neulich nur darüber nachgedacht und wusste nicht, dass andere daran gearbeitet haben. Danke für das Teilen. :)

Michael Wehar

4

Warum glauben Sie, dass es eine geschlossene Formel gibt? Das halte ich für sehr unwahrscheinlich.

Domotorp

Siehe auch diese Frage zu dem, was über dieses Problem bekannt ist: Wie viele Sprachen werden von einem DFA der Größe n akzeptiert

Hermann Gruber,

2

Hier ist eine DFA-bezogene Frage, die ich zuvor hier gestellt habe. Soweit ich weiß, ist sie noch offen:

$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|)$

Diese Frage hat Auswirkungen auf das maschinelle Lernen .

Aryeh
quelle

Wie ist der aktuelle Stand der Komplexität des Problems?

Ryan

1

Jeremiah Blocki hatte einige Teilergebnisse; Soweit ich weiß, ist dies der Stand des Wissens: cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf

Aryeh

-3

("Denken über den Tellerrand" ...) Hierbei handelt es sich um ein Problem, das sich mit DFAs befasst (ich habe es noch nicht anderswo gesehen). In TCS manifestiert sich jedoch ein Thema, bei dem selbst viele scheinbar "einfache" Computerobjekte (wie DFAs) komplexe Eigenschaften haben können , auch ein Aspekt / Thema, das im Satz von Rices enthalten ist. (In gewisser Weise ist die ultimative "Komplexität" "Unentscheidbarkeit", auch bekannt als Turing-Vollständigkeit.)

$n$ $x$ $n$ $x↑n$ ein RE (und damit auch ein DFA). Dieser Operator wird in verschiedenen Zusammenhängen und bei einigen wichtigen Problemen berücksichtigt, z. B. einem der ersten Probleme, die sich als EXPSPACE-vollständig erwiesen haben. [1] [2]

$DFA_n$ $DFA'$ $DFA'$ $n$ $DFA_n$ $DFA'$ wiederholten Instanzen von xist auch ein RL (und ein DFA).

$\Sigma$

$n$ $DFA_n ≠ \Sigma*$

$\Sigma*$ $n$

Nun, um dies besser mit der Frage in Verbindung zu bringen, obgleich dies nicht allgemein zur Kenntnis genommen wird (was von einigen als trivial angesehen wird), sind viele offene Probleme in TCS / Mathematik eng mit der Unentscheidbarkeit verbunden, da sie ein Orakel für das Stopp-Problem sind. " gelöst ".

In gewissem Sinne wird es daher immer offene Probleme mit DFAs geben, wenn dies alles unter Verwendung dieses grundlegenden Problems mit DFAs, das unentscheidbar ist, zusammengeführt wird , da es immer "offene" Probleme mit DFAs (wie diesem) geben wird, die mit unentscheidbaren Problemen äquivalent sind . Tatsächlich kann mit dem Rices-Theorem in umgekehrter Richtung, wie dies in gewisser Weise der Fall ist, jede relativ "einfache", aber nicht triviale Recheneigenschaft in TCS verwendet werden, um unentscheidbare Probleme zu konstruieren.

[1] Wortprobleme, die exponentielle Zeit erfordern / Stockmeyer & Meyer

[2] Meyer, AR und L. Stockmeyer. Das Äquivalenzproblem für reguläre Ausdrücke mit Quadratur erfordert Exponentialraum. 13. IEEE-Symposium über Vermittlung und Automatentheorie, Oktober 1972, S. 125–129.

[3] Einführung in Sprachen, Automaten und Berechnungen / Hopcroft / Ullman.

vzn
quelle

2

Ich denke, Sie verwechseln die Begriffe "unentscheidbar" und "offen".

Lev Reyzin

wie eingeräumt, ist es gelinde gesagt eine ungewöhnliche und / oder unkonventionelle Ansicht, aber ich bin nicht der einzige, der sich dafür ausgesprochen hat. siehe z. B. dieses Zitat von Michel in diesem Aufsatz Probleme in der Zahlentheorie durch geschäftigen Biberwettbewerb . Auch ähnliche Gefühle drückten für berühmte Open-Number-Theory-Vermutungen ein einfaches Problem aus, dessen Unentscheidbarkeit unbekannt ist . siehe auch automatisierter theorem

beweis

D F A_{n} \neq Σ^{*}

$DFA_n \ne \Sigma^*$

n

$n$

{1^{n} ∣ D F A_{n} \neq Σ^{*}}

$\{1^n \mid DFA_n \ne \Sigma^*\}$

D F A^{'}

$DFA'$

Gibt es noch offene Probleme mit DFAs?

Antworten: