minimalizowanie wielkości wyrażeń regularnych dla zbiorów skończonych

Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA .

Jakie są wyniki, jeśli język jest skończony?

Problem ten można rozważyć w dwóch modelach:

1. Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy sumą długości wszystkich ciągów.
2. Dane wejściowe to DFA i mierzymy rozmiar danych wejściowych na podstawie liczby stanów DFA.

Gwiazda Kleene nie jest przydatna w przypadku skończonym, więc only , | i $()$$|$$\cdot$ (konkatenacja) są używane w wyrażeniu. Oczywiście długość wyrażenia regularnego wydaje się dowolna. Zamiast tego można przypisać wagę każdej operacji (w tym dodanie nawiasu) i poprosić o zminimalizowanie wagi wyrażenia regularnego.

Edycja: Jak zauważył adrianN, jest to związane z kodami gramatycznymi. Jest to NP-zupełne, aby utworzyć gramatykę bezkontekstową o minimalnej długości do opisania zbioru skończonego. Nie jest jasne, dlaczego gramatyka bezkontekstowa minimalnego rozmiaru może wiele sugerować o wyrażeniu regularnym minimalnego rozmiaru. Być może sprytna reguła przepisywania może powiązać te dwa i udowodnić, że w pierwszym modelu problemem jest NP.

$\Sigma^P_2$$k$

Uważam, że nie są znane dalsze wyniki dotyczące twoich problemów. W przypadku podobnie wyglądającego problemu optymalizacji, w którym celem jest znalezienie minimalnego równoważnego niedeterministycznego automatu skończonego zamiast wyrażenia regularnego, znane są następujące wyniki:

• ${\bf DP}$${\bf DP}$
• Dla danych wejściowych opisanych jako lista słów minimalnym równoważnym problemem NFA jest ${\bf NP}$
• $L \subseteq \{0,1\}^m$${\bf NP}$

Uwaga: W przeciwieństwie do ustawienia nieskończonych języków, nie widzę prostej redukcji od przypadku minimalizacji NFA do problemów z twojego pytania.

Bibliografia:

(1) Hermann Gruber i Markus Holzer. Złożoność obliczeniowa minimalizacji NFA dla języków skończonych i jednoargumentowych . W: 1. Międzynarodowa konferencja na temat teorii i aplikacji języka i automatów (LATA 2007), s. 261–272, 2007.

(2) Hermann Gruber i Markus Holzer. Niedocenialność niedeterministycznej złożoności stanu i przejścia przy założeniu P <> NP . W: 11. międzynarodowa konferencja nt. Rozwoju teorii języka (DLT 2007), LNCS 4588, s. 205–216, 2007.

$L=\{w\}$$w$ .

najwyraźniej brak dokładnej znanej odpowiedzi lub lepszej od tej, tutaj jest bliski / niedawny przegląd badań dotyczących w szczególności minimalizacji RE (co jest pozornie rzadkim kątem):

Minimalizowanie NFA i wyrażeń regularnych (2005) Gregor Gramlich, Georg Schnitger

Pokazujemy wyniki niedopuszczalności dotyczące minimalizacji niedeterministycznych automatów skończonych (nfa), a także wyrażeń regularnych w stosunku do danych nfa, wyrażeń regularnych lub deterministycznych automatów skończonych (dfa). Pokazujemy, że nie jest możliwe skuteczne zminimalizowanie danego nfa lub wyrażenia regularnego za pomocą n stanów, przejść, względnie. symbole w obrębie współczynnika o (n), chyba że P = PSPACE. Nasze wyniki niedopuszczalności dla danego dfa ze stanami n oparte są na założeniach kryptograficznych i pokazujemy, że każdy wydajny algorytm będzie miał współczynnik aproksymacji co najmniej poli (log n). Nasza konfiguracja pozwala nam również analizować minimalny spójny problem dfa.