Regular expressions with counting: weak versus strong determinism (Q5891559)

The authors of the paper introduce regular expressions with counting that may contain subexpressions of the form \(r^{k,\ell}\) denoting languages \(\bigcup_{i=k}^{\ell} L(r)^i\). They study the notions of strong and weak determinism and show that, except for the unary case, weak determinism is exponentially more succinct and strongly more powerful than strong determinism, even though weakly deterministic regular expressions with counting describe a proper subclass of regular languages. The authors also define nondeterministic and deterministic counter automata recognizing the languages described by regular expressions with counting and strongly deterministic regular expressions with counting, respectively, and study the complexity of union, intersection, complement, and membership and emptiness problem for such automata. Further results concerning regular expressions with counting are as follows: strong determinism can be decided in cubic time; equivalence and inclusion are in PSPACE in the strong deterministic case; intersection is PSPACE-complete in both strong and weak deterministic cases.