Observations on the complexity of regular expression problems

摘要

Several observations are presented on the computational complexity of regular expression problems. The equivalence and containment problems are shown to require more than linear time on any multiple tape deterministic Turing machine. The complexity of the equivalence and containment problems is shown to be “essentially” independent of the structure of the languages represented. Subclasses of the regular grammars, that generate all regular sets but for which equivalence and containment are provably decidable deterministically in polynomial time, are also presented. As corollaries several program scheme problems studied in the literature are shown to be decidable deterministically in polynomial time.