文章基本信息

标题：Transducer-Based Rewriting Games for Active XML
本地全文：下载
作者：Martin Schuster
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：83:1-83:13
DOI：10.4230/LIPIcs.MFCS.2016.83
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：active XML; computational complexity; nested words; transducers; rewriting games