Checking determinism of regular expressions with counting

In this paper, we first present characterizations of weak determinism for regular expressions with counting, based on which we develop an O(|ΣE||E|) time algorithm to check whether an expression E with counting is weakly deterministic, where ΣE is the set of distinct symbols in the expression E. Moreover, our algorithm can locate nondeterminism in subexpressions, which is useful for diagnosing purpose. Then we present a characterization of strong determinism for regular expressions with counting, and study the relations between weak determinism and strong determinism. Based on these, we give an O(|E|) time algorithm to check strong determinism, improving the previous upper bound of O(|E|3) time. Finally, historically there has been another definition of strong determinism for standard regular expressions, which we call restricted strong determinism in this paper. We extend this definition to expressions with counting, establish the relation between the two definitions, and give an O(|E|) time algorithm to check restricted strong determinism for regular expressions with counting.