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:
- Die Eingabe besteht aus allen Zeichenfolgen in der Sprache, und wir messen die Eingabegröße anhand der Summe der Länge aller Zeichenfolgen.
- 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.
Antworten:
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:
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.
quelle
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
quelle