Inclusion of Unambiguous RE#s is NP-Hard
Pekka Kilpeläinen · arXiv (Cornell University) · 2011
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.