The history of schema languages for XML is an increase of expressiveness. While early schema languages mainly focused on element structure, Clark first paid an equal attention to attributes by allowing both element and attribute constraints in the same regular expressions. In this talk, I present our investigatation on the algorithmic aspect of Clark's mechanism (called “attribute-element constraints”), namely, intersection and difference operations and inclusion test, which have been proved to be important in static typechecking for XML processing programs. We present algorithms for these operations that incorporate a “divide-and-conquer” strategy, which is needed to avoid an exponential blow-up that would otherwise happen even for typical inputs. A subtle consequence of adopting this strategy is that we need to alternately switch back and forth between the regular expression and automata representations during the computation.