Pour quelles expressions régulières est PSPACE-complete?

Il est bien connu que le problème suivant est PSPACE-complete:

Étant donné l'expression régulière , ?L ( β ) = Σ $\beta$$L(\beta) = \Sigma^*$

Qu'en est-il de la détermination de l'équivalence avec d'autres expressions régulières (fixes) ?$\alpha$

Étant donné l'expression régulière , ?L ( β ) = L ( α $\beta$$L(\beta) = L(\alpha)$

Ce qui suit est connu:

• Pour , le problème est PSPACE-complet$\alpha = (0+1)^*$

• Pour $\alpha = \emptyset$ , ou plus généralement $\alpha$ qui décrit un ensemble fini, le problème est décidable en temps polynomial.

Il me semble également probable que le problème est en P si $\alpha$ est un langage unaire.

Mes questions sont donc:

Pour quel $\alpha$ le problème de décision ci-dessus est-il complet pour PSPACE? Existe-t-il une caractérisation complète?

Existe-t-il des $\alpha$ pour lesquels le problème de décision a une complexité intermédiaire (comme NP-complete)?

Cette question est abordée dans la section 2 de [1], qui montre (Théorème 2.6) que le problème est

• dans P si est fini;$L(\alpha)$
• coNP-complete si est infini mais borné (ie pour certains );$L(\alpha)$$L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$$w_1,\ldots, w_k$
• PSPACE-complète sinon.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, Sur l'équivalence, le confinement et les problèmes de couverture pour les langages réguliers et sans contexte, Journal of Computer and System Sciences, Volume 12, Issue 2, 1976 , Pages 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4 . ( http://www.sciencedirect.com/science/article/pii/S0022000076800384 )