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

21

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

Étant donné l'expression régulière , ?L ( β ) = Σ βL(β)=Σ

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

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

Ce qui suit est connu:

  • Pour , le problème est PSPACE-completα=(0+1)

  • Pour α= , ou plus généralement α 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 α est un langage unaire.

Mes questions sont donc:

Pour quel α 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 α pour lesquels le problème de décision a une complexité intermédiaire (comme NP-complete)?

mikero
la source
3
Quelles opérations sont autorisées dans vos expressions régulières? Clairement, si vous avez un complément (ou plutôt une différence symétrique), la complexité du problème est indépendante de . α
Emil Jeřábek soutient Monica

Réponses:

17

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(α)
  • coNP-complete si est infini mais borné (ie pour certains );L(α)L(α)w1w2wkw1,,wk
  • 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 )

David
la source
3
Un commentaire sur la réponse précédente (je n'ai pas assez de représentant sur ce site pour commenter): Je ne pense pas que cela puisse être correct. C'est un résultat classique de Meyer-Stockmeyer (Théorème 6.1 de [2]) que l'universalité pour les langues régulières unaires est coNP-complète. [2] LJ Stockmeyer et AR Meyer. 1973. Problèmes de mots nécessitant un temps exponentiel (rapport préliminaire). Dans Actes du cinquième symposium annuel de l'ACM sur la théorie de l'informatique (STOC '73). ACM, New York, NY, USA, 1-9
David
2
J'ai été troublé par votre commentaire car la "réponse précédente" à laquelle vous avez fait référence a été supprimée. Mais de toute façon les langues unaires tombent dans le cas "borné" de votre réponse avec et . k=1|w1|=1
David Eppstein