Inclusion of Unambiguous RE#s is NP-Hard
  We show that testing inclusion between languages represented by regular expressions with numerical occurrence indicators (RE#s) is NP-hard, even if the expressions satisfy the requirement of "unambiguity", which is required for XML Schema content model expressions. 
Pekka Kilpel\"ainen
cs.CC