License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.83
URN: urn:nbn:de:0030-drops-64910
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6491/
Go to the corresponding LIPIcs Volume Portal

Schuster, Martin

Transducer-Based Rewriting Games for Active XML

pdf-format:
LIPIcs-MFCS-2016-83.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{schuster:LIPIcs:2016:6491,
  author =	{Martin Schuster},
  title =	{{Transducer-Based Rewriting Games for Active XML}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6491},
  URN =		{urn:nbn:de:0030-drops-64910},
  doi =		{10.4230/LIPIcs.MFCS.2016.83},
  annote =	{Keywords: active XML, computational complexity, nested words, transducers, rewriting games}
}

Keywords: active XML, computational complexity, nested words, transducers, rewriting games
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI