Active XML schema rewriting based on tree automata theory

An Active XML(AXML for short) is an XML document where some of the data is given explicitly while other parts are defined only intentionally by means of embedded calls to Web services. Introducing intentional data, it brings many new problems to XML documents. The problems of document and schema rewriting are fundamental in practice. In this paper, we try to to solve AXML rewriting problems by using tree automata. Firstly, we define an extended tree automaton, AXML schema tree automaton(ASTA), which can efficiently describe the set of all AXML documents conforming a given schema. Based on ASTA, then we propose an algorithm for deciding one AXML schema can rewrite into the other one performing in polynomial time. Finally, the correctness of our algorithm for checking AXML schema rewriting is also proved.