minimiser la taille de l'expression régulière pour les ensembles finis

Il est connu que minimiser la taille d'une expression régulière est PSPACE-complete même si nous avons un DFA comme spécification du langage .

Quels sont les résultats si la langue est finie?

On peut considérer ce problème dans deux modèles:

1. L'entrée correspond à toutes les chaînes du langage, et nous mesurons la taille d'entrée par la somme de la longueur de toutes les chaînes.
2. L'entrée est un DFA, et nous mesurons la taille de l'entrée par le nombre d'états du DFA.

L'étoile de Kleene n'est pas utile dans le cas fini, donc seulement ,et (concaténation) sont utilisés dans l'expression. Bien sûr, la longueur d'une expression régulière semble arbitraire. Au lieu de cela, on peut donner du poids à chaque opération (inclure l'ajout de parenthèses) et demander de minimiser le poids de l'expression régulière.$()$$|$$\cdot$

Edit: Comme l'a noté adrianN, il est lié aux codes basés sur la grammaire. Il est NP-complet pour produire la grammaire sans contexte de longueur minimale pour décrire un ensemble fini. On ne sait pas pourquoi la grammaire libre de contexte de taille minimale peut impliquer beaucoup sur l'expression régulière de taille minimale. Peut-être qu'une règle de réécriture intelligente peut relier ces deux éléments et prouver que dans le premier modèle, le problème est dans NP.

L'argument suivant provient essentiellement de ( 1 ): Les versions décisionnelles des deux problèmes sont contenues dans le deuxième niveau de la hiérarchie polynomiale (plus précisément: dans la classe de complexité ), comme suit. Devinez une expression régulière de taille au plus k , et vérifiez si elle est équivalente à l'automate fini déterministe donné (respectivement: au langage donné sous forme de liste de mots).$\Sigma^P_2$$k$

Je crois qu'aucun autre résultat concernant vos problèmes n'est connu. Pour un problème d'optimisation d'apparence similaire, où l'objectif est de trouver un automate fini non déterministe équivalent minimum au lieu d'une expression régulière, les résultats suivants sont connus:

• Pour les entrées décrites comme DFA, le problème NFA équivalent minimum est -hard, voir ( 1 ). Ici, D P signifie «différence de temps polynomial»; il s'agit de la classe de complexité "Sigma" au deuxième niveau de la hiérarchie booléenne .${\bf DP}$${\bf DP}$
• Pour une entrée décrite comme une liste de mots, le problème NFA équivalent minimum est -hard, voir ( 2 ).${\bf NP}$
• Pour et l'entrée décrite comme une table de vérité, le problème NFA équivalent minimum est N P - complet, voir ( 2 ).$L \subseteq \{0,1\}^m$${\bf NP}$

Attention: Contrairement au réglage des langues infinies, je ne vois pas de réduction directe du cas de minimisation NFA aux problèmes de votre question.

Les références:

(1) Hermann Gruber et Markus Holzer. Complexité informatique de la minimisation NFA pour les langues finies et unaires . Dans: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber et Markus Holzer. Inapproximabilité de l'état non déterministe et de la complexité de transition en supposant P <> NP . Dans: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

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

manquant apparemment d'une réponse connue exacte ou meilleure que celle-ci, voici une référence proche / récente sur la recherche spécifiquement sur le sujet de la minimisation des RE (qui est un angle apparemment rare):

Minimiser les NFA et les expressions régulières (2005) par Gregor Gramlich, Georg Schnitger

Nous montrons des résultats d'inapproximabilité concernant la minimisation des automates finis non déterministes (nfa) ainsi que des expressions régulières par rapport aux nfa donnés, des expressions régulières ou des automates finis déterministes (dfa). Nous montrons qu'il est impossible de minimiser efficacement une nfa donnée ou une expression régulière avec n états, transitions, resp. symboles dans le facteur o (n), sauf si P = ESPACE. Nos résultats d'inapproximabilité pour un dfa donné avec n états sont basés sur des hypothèses cryptographiques et nous montrons que tout algorithme efficace aura un facteur d'approximation d'au moins poly (log n). Notre configuration nous permet également d'analyser le problème de dfa cohérent minimum.