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

15

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:

Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy sumą długości wszystkich ciągów.
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.

— Chao Xu
źródło

3

Wydaje się, że jest to związane z kodami opartymi na gramatyce .

— adrianN

załóżmy, że rozmiar wejściowy jest ograniczony. wtedy gwiazda Kleene może być ważna. więc sensowne jest określenie, czy rozmiar wejściowy jest (naturalnie) ograniczony do najdłuższego ciągu w skończonym języku. a także jeśli w tym przypadku nadal wykluczana jest gwiazda Kleene. również, jako (oczywista?) heurystyka, minimalizowanie DFA i konstruowanie RE z tego jest jedną strategią ... zauważ również, że RE (ze zmiennym podstawieniem) mają strukturę podobną do DAG i nie ma wielu (mocnych) thms o minimalizację DAG struktury przypominające .... RE bez zmiennego zastąpienie treelike (wzory) i może być łatwiej pracować ....

— vzn

inny kąt. Wiadomo, że „pochodne RE” wprowadzone przez Brzozowskiego są przydatne do przekształcania RE bezpośrednio w DFA, patrz np. Pochodne o regularnej ekspresji badane ponownie przez Owensa, Reppy'ego, Turona. może jest jakiś sposób na użycie tej samej struktury dla odwrotnego problemu. w każdym razie, choć ogólnie wydaje się, że jest to otwarty problem ....

— dniu

4

$\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$ .

— Hermann Gruber
źródło

-6

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.

— vzn
źródło

4

To pytanie zostało zadane konkretnie, ponieważ ten artykuł nie dotyczy tego, co dzieje się, gdy język jest skończony.

— Chao Xu,

1

dobrze, to służy jako [odpowiedni / nigdzie] bkg. zauważ jednak, że jeśli na drugie pytanie nie ma [opublikowanej] odpowiedzi, to z pewnością nie dziwi to, że kąt prawie odmienny może niewiele pomóc. również [ mea culpa ] nie zauważył, że artykuł został zacytowany przez MdB na inne pytanie.

— wzn