LIPIcs.MFCS.2016.83.pdf
- Filesize: 487 kB
- 13 pages
Document
Transducer-Based Rewriting Games for Active XML
Author
-
Part of:
Volume:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-19
Cite As Get BibTex
Martin Schuster. Transducer-Based Rewriting Games for Active XML. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.83
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.
Subject Classification
Keywords
- active XML
- computational complexity
- nested words
- transducers
- rewriting games
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Serge Abiteboul, Omar Benjelloun, and Tova Milo. The Active XML project: an overview. VLDB J., 17(5):1019-1040, 2008. URL: http://dx.doi.org/10.1007/s00778-007-0049-y.
- Serge Abiteboul, Tova Milo, and Omar Benjelloun. Regular rewriting of active XML and unambiguity. In PODS, pages 295-303, 2005. URL: http://dx.doi.org/10.1145/1065167.1065204.
- Rajeev Alur and P. Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009. URL: http://dx.doi.org/10.1145/1516512.1516518.
- Henrik Björklund, Martin Schuster, Thomas Schwentick, and Joscha Kulbatzki. On optimum left-to-right strategies for active context-free games. In ICDT, pages 105-116, 2013. URL: http://dx.doi.org/10.1145/2448496.2448510.
- Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais, and Jean-Marc Talbot. Properties of visibly pushdown transducers. In MFCS, pages 355-367, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15155-2_32.
- Tova Milo, Serge Abiteboul, Bernd Amann, Omar Benjelloun, and Frederic Dang Ngoc. Exchanging intensional XML data. ACM Trans. Database Syst., 30(1):1-40, 2005. URL: http://dx.doi.org/10.1145/1061318.1061319.
- Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Active context-free games. Theory Comput. Syst., 39(1):237-276, 2006. URL: http://dx.doi.org/10.1007/s00224-005-1278-3.
- Jean-François Raskin and Frédéric Servais. Visibly pushdown transducers. In ICALP (2), pages 386-397, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_32.
- Martin Schuster. Transducer-based rewriting games for Active XML. CoRR, abs/1606.02879, 2016. URL: http://arxiv.org/abs/1606.02879.
- Martin Schuster and Thomas Schwentick. Games for Active XML revisited. In ICDT, pages 60-75, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.60.
- Frédéric Servais. Visibly pushdown transducers. Dissertation, ULB Belgique, 2011. URL: http://theses.ulb.ac.be/ETD-db/collection/available/ULBetd-09292011-142239/.
- Alex Thomo, S. Venkatesh, and Ying Ying Ye. Visibly pushdown transducers for approximate validation of streaming xml. In FoIKS, pages 219-238, Berlin, Heidelberg, 2008. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1786094.1786112.