On optimum left-to-right strategies for active context-free games

Henrik Björklund, Martin Schuster, Thomas Schwentick, Joscha Kulbatzki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 16th International Conference on Database Theory
PublisherACM
Pages105-116
Number of pages12
ISBN (Electronic)978-1-4503-1598-2
DOIs
Publication statusPublished - 18 Mar 2013
Event6th International Conference on Database Theory - Genoa, Italy
Duration: 18 Mar 201322 Mar 2013
http://edbticdt2013.disi.unige.it/

Conference

Conference6th International Conference on Database Theory
Abbreviated titleICDT 2013
CountryItaly
CityGenoa
Period18/03/1322/03/13
Internet address

Fingerprint

Dive into the research topics of 'On optimum left-to-right strategies for active context-free games'. Together they form a unique fingerprint.

Cite this