Algoritmo para determinar se dois regexes são equivalentes

Dadas duas expressões regulares arbitrárias, existe um algoritmo "eficiente" para determinar se elas correspondem ao mesmo conjunto de cadeias?

De maneira mais geral, podemos calcular o tamanho da interseção dos dois conjuntos de correspondências?

Quais algoritmos existem para fazer isso e em que classe de complexidade eles vivem?

Se recusarmos a estrela Kleene, isso altera a imagem?

Hendrik Jan fornece uma boa resposta para a classe de complexidade, mas não um algoritmo em si.

O algoritmo mais simples de fazer isso que eu sei é converter a expressão regular em um DFA. Existem técnicas conhecidas para converter uma expressão regular em um NFA e um NFA em um DFA.

Depois de ter dois DFAs, o teste de equivalência é eficiente e decidível, pois a forma mínima de um DFA é exclusiva até o isomorfismo.

No entanto, a construção desses DFAs a partir de NFAs pode levar muito tempo e produzir DFAS extremamente grandes, exponencialmente grandes no pior caso.

Sabe-se que a equivalência de expressões regulares é completa no PSPACE, o que é bastante ruim. O artigo "Complexidade de problemas de decisão para expressões regulares simples" lista várias subclasses de expressões regulares com suas respectivas complexidades. ( link )