NFA-DFA-Powerset-Konstruktion: Ein partieller Bestimmungsalgorithmus mit Kompromiss zwischen Laufzeit und Größe für die resultierenden Automaten?

Bei einem NFA und seinem äquivalenten DFA die sich aus der Gesamtbestimmung von (z. B. unter Verwendung der Powerset-Konstruktion), gelten die folgenden Eigenschaften für , und für jedes Wort : $N$ $D$ $N$ $N$ $D$ $w$

$N$ liest in der Laufzeit höchstens . $w$ $O(|w|.|N|^2)$
$D$ liest $w$ in der Laufzeit höchstens $O(|w|)$ und seine Größe kann $O(2^{|N|})$ (in der Anzahl der Zustände, die zur Darstellung von benötigt werden $D$ ).

Ich frage mich, ob es einen partiellen Determinierungsalgorithmus gibt, der einen Kompromiss zwischen der Größe des Ergebnisses und der Laufzeit garantiert.

Zum Beispiel könnte dieser partielle Determinierungsalgorithmus eine NFA in teilweise deterministische Automaten verwandeln $D'$ so dass $D'$ garantiert, dass das Wort $w$ in gelesen wird, $O(|w|.|N|^x)$ wobei $0 \leq x \leq 2$ ohne die Größe zu überschreiten $|D'| \leq 2^{f(x)}$ wobei $f(x)$ eine kontinuierlich abnehmende Funktion ist, die im Bereich $[0, 2]$ so dass $f(0)=|N|$ und $f(2)=log |N|$ .

Ich habe keine Methode gefunden, um eine NFA teilweise so zu bestimmen. In allen Veröffentlichungen: Jede Determinierung wird vermieden, weil die NFA zu groß ist, jede Determinierung ist voll und die NFA wird in eine DFA umgewandelt (mit einer möglichen exponentiellen Explosion). Es gibt keinen Kompromiss ...

Ich würde mich über Referenzen oder Antworten zu diesem Problem sehr freuen. Vielen Dank, Luz.

automata-theory regular-language nondeterminism dfa nfa Luz
quelle

Ist cstheory.stackexchange.com/a/1273/236 nützlich?

Radu GRIGore

Wow :-) das ist großartig! In der Tat scheint der Beitrag cstheory.stackexchange.com/questions/1132/… den Job zu erledigen. Vielen Dank, ich werde die Antwort von D. Eppstein verarbeiten ...

Luz

Das Papier [HP06] ist im Geiste Ihrer Idee, wenn auch in eine andere Richtung, im Kontext unendlicher Wörter. Es kann leichter an endliche Wörter angepasst werden.

Bei der Powerset-Konstruktion verfolgen wir gleichzeitig alle möglichen Läufe des Zustandsautomaten, indem wir uns um Token bewegen . Wir könnten uns jedoch entscheiden, nur Läufen zu folgen und eine partielle Powerset-Konstruktion durchzuführen. Im Allgemeinen ergibt dies einen nicht deterministischen Automaten, der nicht wirklich nützlicher ist als der ursprüngliche. $n$ $n$ $k<n$

Es könnte jedoch sein, dass das Erstellen von Läufen mit einer bestimmten deterministischen Strategie immer ausreicht, um eine akzeptierende zu erhalten, falls eine existiert. Stellen Sie sich zum Beispiel einen großen Automaten vor, bei dem der einzige Nichtdeterminismus darin besteht, zu erraten, ob der letzte Buchstabe oder a , und dann zu zwei deterministischen Automaten zu verzweigen. Dann genügen zwei Token, und eine Potenzsatz-Konstruktion funktioniert, bei der Teilmengen höchstens , dh der resultierende Automat hat -Zustände. $k$ $a$ $b$ $2$ $2$ $\dfrac{n(n+1)}{2}$

Wir können die "Breite" eines nicht deterministischen Automaten als die Anzahl der Token definieren, die benötigt werden, um einen akzeptierenden Lauf deterministisch aufzubauen. Die Powerset-Konstruktion geht tatsächlich davon aus, dass wir uns im schlimmsten Fall befinden, dh die Breite entspricht der Anzahl der Zustände. Der Fall, in dem die Breite beträgt, entspricht dem in [HP06] eingeführten und in [BKKS13, KS15] weiter untersuchten Begriff des GFG-Automaten (Good-for-Games). $1$

Wir haben, dass ein NFA genau dann eine Breite von höchstens wenn seine Powerset-Konstruktion GFG ist. Bei endlichen Wörtern ist es in P zu erkennen, ob ein Automat GFG ist, und in diesem Fall bedeutet dies tatsächlich, dass er mit einigen zusätzlichen nutzlosen Übergängen deterministisch ist. Dies bedeutet, dass wir inkrementieren können, bis die resultierende Powerset-Konstruktion GFG ist, die nutzlosen Übergänge beschneiden und einen deterministischen Automaten erhalten. Dies entspricht der Betonung der Platzersparnis, da wir, anstatt den großen deterministischen Automaten zu bauen und ihn dann zu minimieren, versuchen, ihn "von unten" anzusprechen, in der Hoffnung, dass wir nicht die vollständige Powerset-Konstruktion durchführen müssen. $k$ $k$ $k$ $k$

[HP06] Spiele ohne Bestimmung lösen, Henzinger, Piterman, in CSL 2006

[BKKS13] Nichtdeterminismus in Gegenwart einer vielfältigen oder unbekannten Zukunft , Böker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013

[KS15] Zur Bestimmung von Spielautomaten , Kuperberg, Skrzypczak, in ICALP 2015

Denis
quelle

Vielen Dank für Ihren Beitrag :-), aber ich brauche etwas mehr Hilfe, um das Gesamtbild Ihrer Vorschläge zu verstehen. Ich möchte auch die Hauptunterschiede zwischen Ihrem Beitrag und dem von D. Eppstein (wie im oberen Kommentar vorgeschlagen) hier verstehen : cstheory.stackexchange.com/questions/1132/… .

Luz

Wenn ich die DE (D. Eppstein) -Methode zusammenfasse: Bei einer NFA der Größe , und einem Wort der Größe garantiert die DE-Methode einen Kompromiss zwischen einer NFA-Simulationszeit von und eine Größe von zum Speichern der Datenstruktur, die die NFA darstellt (obwohl diese Datenstruktur keine NFA ist, ist sie ein Array).

n

$n$

1 \leq x \leq n

$1 \leq x \leq n$

w

$w$

O (w . x^{2})

$O(w.x^2)$

O (x^{2} {.2}^{n / x})

$O(x^2.2^{n/x})$

Luz

Da sind meine Fragen. Bei einer NFA mit Breite der Größe ist (1) die maximale Größe des resultierenden DFA von der -powerset Konstruktion angewandt auf ? Und (2) ist die maximale Zeit, die benötigt wird, um zu simulieren ?

k

$k$

N

$N$

n

$n$

S = O (\sum_{i = 0}^{k} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{k}{{n}\choose{i}})$

k

$k$

N

$N$

T = O (w . k)

$T=O(w.k)$

N

$N$

Luz

Zusätzliche Frage, ob die beiden vorherigen Hypothesen wahr sind. Stellen Sie sich einen Anwendungsfall vor, in dem der verfügbare Raum zur Bestimmung von so festgelegt ist, dass mit . Dann bestimmen wir teilweise in indem wir die Powerset-Konstruktion auf anwenden (da dafür genügend Platz vorhanden ist). Ist die maximale Zeit, die benötigt wird, um zu simulieren ?

S

$S$

N

$N$

S = O (\sum_{i = 0}^{p} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{p}{{n}\choose{i}})$

p \leq k

$p \leq k$

N

$N$

N^{'}

$N'$

p

$p$

N

$N$

O (w . (k / p))

$O(w.(k/p))$

N^{'}

$N'$

Luz

(1) Ja (2) Sie sind sich nicht sicher, was Sie unter "simulieren" verstehen, aber Sie können k Token in N deterministisch verschieben, um zu sehen, ob ein Wort akzeptiert wird. Daher würde ich "Ja" sagen. (3) Ja, mit einer Obergrenze für k / p

Denis

NFA-DFA-Powerset-Konstruktion: Ein partieller Bestimmungsalgorithmus mit Kompromiss zwischen Laufzeit und Größe für die resultierenden Automaten?

Antworten: