This paper presents a new algorithm for the containment problem for extended regular expressions that contain intersection and complement operators and that range over infinite alphabets. The algorithm solves extended regular expressions inequalities symbolically by term rewriting and thus avoids the translation to an expression-equivalent automaton.Our algorithm is based on Brzozowskiu27s regular expression derivatives and on Antimirovu27s term-rewriting approach to check containment. To deal with large or infinite alphabets effectively, we generalize Brzozowskiu27s derivative operator to work with respect to (potentially infinite) representable character sets.
展开▼
