Efficient testing and matching of deterministic regular expressions

A linear time algorithm is presented for testing determinism of a regular expression. It is shown that an input word of length n can be matched against a deterministic regular expression of length m in time O(m+nlog⁡log⁡m). If the deterministic regular expression has bounded depth of alternating union and concatenation operators, then matching can be performed in time O(m+n). These results extend to regular expressions containing numerical occurrence indicators.