minimizando o tamanho da expressão regular para conjuntos finitos

15

Sabe-se que minimizar o tamanho de uma expressão regular é completo no PSPACE, mesmo que tenhamos um DFA como especificação da linguagem .

Quais são os resultados se o idioma for finito?

Pode-se considerar esse problema em dois modelos:

  1. A entrada é todas as strings do idioma e medimos o tamanho da entrada pela soma do comprimento de todas as strings.
  2. A entrada é um DFA e medimos o tamanho da entrada pelo número de estados do DFA.

A estrela Kleene não é útil no caso finito; portanto, somente , | e (concatenação) são usados ​​na expressão. Obviamente, o tamanho de uma expressão regular parece arbitrário. Em vez disso, pode-se dar peso a cada operação (incluindo adicionar parênteses) e pedir para minimizar o peso da expressão regular.()|

Edit: Como adrianN observou, está relacionado a códigos baseados em gramática. É NP-completo produzir a gramática livre de contexto de comprimento mínimo para descrever um conjunto finito. Não está claro por que a gramática livre de contexto de tamanho mínimo pode implicar muito na expressão regular de tamanho mínimo. Talvez uma regra inteligente de reescrita possa relacionar esses dois e provar que, no primeiro modelo, o problema está no NP.

Chao Xu
fonte
3
Isso parece relacionado a códigos baseados em gramática .
Adriann
suponha que o tamanho da entrada seja limitado. então kleene star pode ser válida. portanto, faz sentido definir se o tamanho da entrada é (naturalmente) limitado à string mais longa no idioma finito. & também se kleene star ainda estiver excluída nesse caso. Além disso, como uma heurística (óbvia?), minimizar o DFA e construir uma ER a partir dessa estratégia ... observe também que as ERs (com substituição variável) têm uma estrutura semelhante a DAG e não existem muitos thms (fortes) conhecidos sobre como minimizar DAG-like estruturas .... REs sem substituição de variáveis são treelike (fórmulas) e pode ser mais fácil trabalhar com ....
vzn
outro ângulo. Sabe-se que os "derivados de RE" introduzidos por brzozowski são úteis para converter REs diretamente em DFAs, por exemplo , derivados de expressão regular reexaminados por Owens, Reppy, Turon. talvez exista alguma maneira de usar a mesma estrutura para o problema inverso. de qualquer maneira, embora, em geral, parece ser um problema em aberto ....
vzn

Respostas:

4

Σ2Pk

Acredito que não sejam conhecidos mais resultados sobre seus problemas. Para um problema de otimização de aparência semelhante, em que o objetivo é encontrar um autômato finito não determinístico equivalente ao invés de uma expressão regular, os seguintes resultados são conhecidos:

  • DPDP
  • Para entradas descritas como uma lista de palavras, o problema mínimo equivalente de NFA é NP
  • eu{0 0,1}mNP

Cuidado: ao contrário da configuração de idiomas infinitos, não vejo uma redução direta do caso de minimização da NFA aos problemas de sua pergunta.

Referências:

(1) Hermann Gruber e Markus Holzer. Complexidade Computacional da Minimização de NFA para Idiomas Finitos e Unários . In: 1ª Conferência Internacional sobre Linguagem e Teoria de Autômatos e Aplicações (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber e Markus Holzer. Inaproximabilidade do estado não determinístico e da complexidade de transição assumindo P <> NP . In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

eu={W}W .

Hermann Gruber
fonte
-6

aparentemente sem uma resposta exata exata ou melhor que essa, aqui está uma referência próxima / recente à pesquisa especificamente sobre o objetivo de minimizar os REs (que é um ângulo aparentemente incomum):

Minimizando as AFN e as expressões regulares (2005) de Gregor Gramlich, Georg Schnitger

Mostramos resultados de inadequação relativos à minimização de autômatos finitos não determinísticos (nfa), bem como expressões regulares relativas a determinados nfa, expressões regulares ou autômatos finitos determinísticos (dfa). Mostramos que é impossível minimizar com eficiência um determinado nfa ou expressão regular com n estados, transições, resp. símbolos dentro do fator o (n), a menos que P = PSPACE. Nossos resultados de inadequação para um dado dfa com n estados são baseados em suposições criptográficas e mostramos que qualquer algoritmo eficiente terá um fator de aproximação de pelo menos poli (log n). Nossa configuração também nos permite analisar o problema mínimo consistente de dfa.

vzn
fonte
4
Esta pergunta foi feita especificamente porque este artigo não aborda o que acontece quando o idioma é finito.
Chao Xu #
1
bem, então serve como [relevante / nec] bkg. mas observe que, se a outra pergunta não tiver resposta [publicada], certamente não surpreende que essa também não seja, um ângulo de variante próximo pode não ajudar muito. também [ mea culpa ] não notou que o trabalho foi citado por MdB na outra questão.
vzn