Transducer-Based Rewriting Games for Active XML

Martin Schuster

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Context-free games are two-player rewriting games that are played on nested strings representing XML documents with embedded function symbols. These games were introduced to model rewriting processes for intensional documents in the Active XML framework, where input documents are to be rewritten into a given target schema by calls to external services. This paper studies the setting where dependencies between inputs and outputs of service calls are modelled by transducers, which has not been examined previously. It defines transducer models operating on nested words and studies their properties, as well as the computational complexity of the winning problem for transducer-based context-free games in several scenarios. While the complexity of this problem is quite high in most settings (ranging from NP-complete to undecidable), some tractable restrictions are also identified.
Original languageEnglish
Title of host publication41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
EditorsPiotr Faliszewski, Anca Muscholl, Rolf Niedermeier
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Number of pages13
ISBN (Print)978-3-95977-016-3
Publication statusPublished - 26 Aug 2016
Event41st International Symposium on Mathematical Foundations of Computer Science - Krakow, Poland
Duration: 22 Aug 201626 Aug 2016

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISSN (Electronic)1868-8969


Conference41st International Symposium on Mathematical Foundations of Computer Science
Abbreviated titleMFCS 2016
Internet address


Dive into the research topics of 'Transducer-Based Rewriting Games for Active XML'. Together they form a unique fingerprint.

Cite this