On optimum left-to-right strategies for active context-free games
2013 (English)In: ICDT '13 Proceedings of the 16th International Conference on Database Theory, ACM Press, 2013, 105-116 p.Conference paper (Refereed)
Active context-free games are two-player games on strings over finite alphabets with one player trying to rewrite the input string to match a target specification. These games have been investigated in the context of exchanging Active XML (AXML) data. While it was known that the rewriting problem is undecidable in general, it is shown here that it is EXPSPACE-complete to decide for a given contextfree game, whether all safely rewritable strings can be safely rewritten in a left-to-right manner, a problem that was previously considered by Abiteboul et al. Furthermore, it is shown that the corresponding problem for games with finite replacement languages is EXPTIME-complete.
Place, publisher, year, edition, pages
ACM Press, 2013. 105-116 p.
, ACM International Conference Proceeding Series
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-71146DOI: 10.1145/2448496.2448510ISBN: 978-1-4503-1598-2OAI: oai:DiVA.org:umu-71146DiVA: diva2:622174
16th International Conference on Database Theory, ICDT 2013, Genoa, Italy, 18 March 2013 through 22 March 2013