Change search
ReferencesLink to record
Permanent link

Direct link
On optimum left-to-right strategies for active context-free games
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Technische Universität Dortmund.
Technische Universität Dortmund.
SCISYS Deutschland GmbH.
2013 (English)In: ICDT '13 Proceedings of the 16th International Conference on Database Theory, ACM Press, 2013, 105-116 p.Conference paper (Refereed)
Abstract [en]

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
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:umu:diva-71146DOI: 10.1145/2448496.2448510ISBN: 978-1-4503-1598-2OAI: diva2:622174
16th International Conference on Database Theory, ICDT 2013, Genoa, Italy, 18 March 2013 through 22 March 2013
Available from: 2013-05-20 Created: 2013-05-20 Last updated: 2013-11-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Björklund, Henrik
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link