Minimierung der Größe des regulären Ausdrucks für endliche Mengen

15

Es ist bekannt, dass die Minimierung der Größe eines regulären Ausdrucks PSPACE-vollständig ist, auch wenn wir einen DFA als Sprachspezifikation haben .

Was sind die Ergebnisse, wenn die Sprache endlich ist?

Man kann dieses Problem in zwei Modellen betrachten:

  1. Die Eingabe besteht aus allen Zeichenfolgen in der Sprache, und wir messen die Eingabegröße anhand der Summe der Länge aller Zeichenfolgen.
  2. Die Eingabe ist ein DFA, und wir messen die Eingabegröße anhand der Anzahl der Zustände des DFA.

Kleene star ist im endlichen Fall nicht sinnvoll, also only ,und (Verkettung) werden im Ausdruck verwendet. Natürlich scheint die Länge eines regulären Ausdrucks willkürlich zu sein. Stattdessen kann jeder Operation eine Gewichtung zugewiesen werden (einschließlich des Hinzufügens von Klammern) und das Minimieren der Gewichtung des regulären Ausdrucks verlangt werden.()|

Bearbeiten: Wie adrianN angemerkt hat, handelt es sich um grammatikbasierte Codes. Es ist NP-vollständig, die kontextfreie Grammatik mit minimaler Länge zu erzeugen, um eine endliche Menge zu beschreiben. Es ist nicht klar, warum kontextfreie Grammatik mit minimaler Größe viel über reguläre Ausdrücke mit minimaler Größe aussagen kann. Vielleicht kann eine clevere Regel zum Umschreiben diese beiden Regeln in Beziehung setzen und beweisen, dass das Problem im ersten Modell in NP liegt.

Chao Xu
quelle
3
Dies scheint mit grammatikbasierten Codes zu tun zu haben .
AdrianN
Angenommen, die Eingabegröße ist begrenzt. dann könnte kleene star gültig sein. Daher ist es sinnvoll zu definieren, ob die Eingabegröße (natürlich) auf die längste Zeichenfolge in der endlichen Sprache beschränkt ist. & auch wenn kleene star in diesem fall noch ausgeschlossen ist. Als (offensichtliche?) Heuristik ist es auch eine Strategie, den DFA zu minimieren und eine RE daraus zu konstruieren. Beachten Sie auch, dass REs (mit variabler Substitution) eine DAG-ähnliche Struktur haben und es nicht viele (starke) ThMS gibt über die Minimierung von DAG-ähnlichen Strukturen .... REs ohne variable Substitution sind baumähnlich (Formeln) und können möglicherweise einfacher bearbeitet werden ....
vzn
anderer Winkel. Von brzozowski eingeführte RE- "Derivate" sind bekanntermaßen nützlich, um REs direkt in DFAs umzuwandeln, siehe z. B. Derivate mit regulärer Expression, die von Owens, Reppy, Turon erneut untersucht wurden. Vielleicht gibt es eine Möglichkeit, dieselbe Struktur für das inverse Problem zu verwenden.
Trotzdem

Antworten:

4

Σ2Pk

Ich glaube, dass keine weiteren Ergebnisse bezüglich Ihrer Probleme bekannt sind. Für ein ähnlich aussehendes Optimierungsproblem, bei dem das Ziel darin besteht, anstelle eines regulären Ausdrucks ein Minimumäquivalent eines nicht deterministischen endlichen Automaten zu finden, sind die folgenden Ergebnisse bekannt:

  • DPDP
  • NP
  • L{0,1}mNP

Achtung: Im Gegensatz zur Einstellung von unendlichen Sprachen sehe ich keine direkte Reduktion vom Fall der NFA-Minimierung auf die Probleme aus Ihrer Frage.

Verweise:

(1) Hermann Gruber und Markus Holzer. Computerkomplexität der NFA-Minimierung für endliche und unäre Sprachen . In: 1. Internationale Konferenz über Sprach- und Automatentheorie und -anwendungen (LATA 2007), S. 261-272, 2007.

(2) Hermann Gruber und Markus Holzer. Inapproximierbarkeit nichtdeterministischer Zustände und Übergangskomplexität unter Annahme von PNP . In: 11. Internationale Konferenz über Entwicklungen in der Sprachtheorie (DLT 2007), LNCS 4588, S. 205-216, 2007.

L={w}w .

Hermann Gruber
quelle
-6

Da es anscheinend an einer genau bekannten Antwort mangelt oder eine bessere Antwort als diese, ist hier ein aktueller Hinweis auf Forschungsergebnisse speziell zum Thema der Minimierung von REs (was ein anscheinend ungewöhnlicher Aspekt ist):

Minimierung von NFAs und regulären Ausdrücken (2005) von Gregor Gramlich, Georg Schnitger

Wir zeigen inapproximability Ergebnisse bezüglich der Minimierung von nicht deterministischen endlichen Automaten (nfa) sowie regulären Ausdrücken relativ zu gegebenen nfa, regulären Ausdrücken oder deterministischen endlichen Automaten (dfa). Wir zeigen, dass es unmöglich ist, eine gegebene nfa oder einen regulären Ausdruck mit n Zuständen, Übergängen, resp. Symbole innerhalb des Faktors o (n), außer P = PSPACE. Unsere Inapproximierbarkeitsergebnisse für einen gegebenen dfa mit n Zuständen basieren auf kryptographischen Annahmen und wir zeigen, dass jeder effiziente Algorithmus einen Approximationsfaktor von mindestens poly (log n) hat. Mit unserem Setup können wir auch das minimale konsistente DFA-Problem analysieren.

vzn
quelle
4
Diese Frage wurde speziell gestellt, weil in diesem Artikel nicht behandelt wird, was passiert, wenn die Sprache endlich ist.
Chao Xu
1
gut, dann dient es als [relevant / ang] bkg. Aber beachten Sie, dass, wenn die andere Frage keine [veröffentlichte] Antwort hat, dies sicherlich auch nicht verwunderlich ist, ein nahezu variantenreicher Winkel möglicherweise nicht viel hilft. auch [ mea culpa ] bemerkte nicht, dass das Papier von MdB zu der anderen Frage zitiert wurde.
vzn