Document Open Access Logo

Games for Active XML Revisited

Authors Martin Schuster, Thomas Schwentick

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.60.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Martin Schuster
Thomas Schwentick

Cite As Get BibTex

Martin Schuster and Thomas Schwentick. Games for Active XML Revisited. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 60-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.60

Abstract

The paper 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 paper 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 paper examines several extensions to active context-free games.

The primary extension allows 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 service call results.

In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the paper identifies interesting tractable cases.

Subject Classification

Keywords
  • Active XML
  • Computational Complexity
  • Nested Words
  • Rewriting Games
  • Semistructured Data

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Omar Benjelloun, and Tova Milo. The Active XML project: an overview. VLDB J., 17(5):1019-1040, 2008. Google Scholar
  2. Serge Abiteboul, Tova Milo, and Omar Benjelloun. Regular rewriting of active XML and unambiguity. In PODS, pages 295-303, 2005. Google Scholar
  3. Rajeev Alur and P. Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009. Google Scholar
  4. Henrik Björklund, Martin Schuster, Thomas Schwentick, and Joscha Kulbatzki. On optimum left-to-right strategies for active context-free games. In Joint 2013 EDBT/ICDT Conferences, ICDT '13 Proceedings, Genoa, Italy, March 18-22, 2013, pages 105-116, 2013. Google Scholar
  5. Laura Bozzelli. Alternating automata and a temporal fixpoint calculus for visibly pushdown languages. In CONCUR- Concurrency Theory, 18th International Conference, pages 476-491, 2007. Google Scholar
  6. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logics, and Infinite Games. A Guide to Current Research. Springer, 2002. Google Scholar
  7. Lukasz Kaiser. Synthesis for structure rewriting systems. In Rastislav Královic and Damian Niwinski, editors, MFCS, volume 5734 of Lecture Notes in Computer Science, pages 415-426. Springer, 2009. Google Scholar
  8. Wim Martens, Frank Neven, Thomas Schwentick, and Geert Jan Bex. Expressiveness and complexity of XML schema. ACM Trans. Database Syst., 31(3):770-813, 2006. Google Scholar
  9. 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. Google Scholar
  10. Makoto Murata, Dongwon Lee, Murali Mani, and Kohsuke Kawaguchi. Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Techn., 5(4):660-704, 2005. Google Scholar
  11. Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Active context-free games. Theory Comput. Syst., 39(1):237-276, 2006. Google Scholar
  12. Martin Schuster and Thomas Schwentick. Games for Active XML revisited. CoRR, abs/1412.5910, 2014. Available online at URL: http://arxiv.org/abs/1412.5910.
  13. Johannes Waldmann. Rewrite games. In Sophie Tison, editor, RTA, volume 2378 of Lecture Notes in Computer Science, pages 144-158. Springer, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact