Games for Active XML Revisited

Martin Schuster, Thomas Schwentick

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The article studies the rewriting mechanisms for intensional documents in the Active XML framework, abstracted in the form of active context-free games. The safe rewriting problem studied in this article is to decide whether the first player, JULIET, has a winning strategy for a given game and (nested) word; this corresponds to a successful rewriting strategy for a given intensional document. The article examines several extensions of active context-free games. The primary extension allows for more expressive schemas (namely XML schemas and regular nested word languages) for both target and replacement languages and has the effect that games are played on nested words instead of (flat) words as in previous studies. Other extensions consider validation of input parameters of web services, and an alternative semantics based on insertion of values returned by the services. In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the article identifies relevant tractable cases.
Keywords Active XML · Computational complexity · Nested words · Rewriting games · Semistructured data
Original languageEnglish
Pages (from-to)84-155
Number of pages72
JournalTheory of Computing Systems
Issue number1
Early online date4 Aug 2016
Publication statusPublished - 2017


Dive into the research topics of 'Games for Active XML Revisited'. Together they form a unique fingerprint.

Cite this