Abstract: The problem of schema rewriting is a fundamental and usually has a higher complexity. We defined an extended problem of Active XML（AXML for short） data exchange tree automaton,AXML schema tree automaton（ASTA）, which can efficiently describe the set of all

Key words: Active XML, Active XML schema, Tree automata, Schema rewriting