Regular Rewriting of Active XML and Unambiguity Serge Abiteboul   View Paper (PDF)   Return to Research Session 8: Information Processing on the Web Abstract We consider here the exchange of Active XML (AXML) data, i.e., XML documents where some of the data is given explicitly while other parts are given only intensionally as calls to Web services. Peers exchanging AXML data agree on a data exchange schema that specifies in particular which parts of the data are allowed to be intensional. Before sending a document, a peer may need to rewrite it to match the agreed data exchange schema, by calling some of the services and materializing their data. Previous works showed that the rewriting problem is undecidable in the general case and of high complexity in some restricted cases. We argue here that this difficulty is somewhat artificial. Indeed, we study what we believe to be a more adequate, from a practical view point, rewriting problem that is (1) in the spirit of standard 1-unambiguity constraints imposed on XML schema and (2) can be solved by a single pass over the document with a computational device not stronger than a finite state automaton. Following previous works, we focus on the core of the problem, i.e., on the problem on words. The resultsmay be extended to (A)XML trees in a straightforward manner. ©2006 Association for Computing Machinery