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

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

doi:10.1145/2448496.2448510

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 proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 16th International Conference on Database Theory
Publisher	ACM
Pages	105-116
Number of pages	12
ISBN (Electronic)	978-1-4503-1598-2
DOIs	https://doi.org/10.1145/2448496.2448510
Publication status	Published - 18 Mar 2013
Event	6th International Conference on Database Theory - Genoa, Italy Duration: 18 Mar 2013 → 22 Mar 2013 http://edbticdt2013.disi.unige.it/

Conference

Conference	6th International Conference on Database Theory
Abbreviated title	ICDT 2013
Country/Territory	Italy
City	Genoa
Period	18/03/13 → 22/03/13
Internet address	http://edbticdt2013.disi.unige.it/

Access to Document

10.1145/2448496.2448510

https://dl.acm.org/citation.cfm?doid=2448496.2448510

Cite this

@inproceedings{109ae23931bc4bf3ae2c8e2bc9b48354,

title = "On optimum left-to-right strategies for active context-free games",

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.",

author = "Henrik Bj{\"o}rklund and Martin Schuster and Thomas Schwentick and Joscha Kulbatzki",

year = "2013",

month = mar,

day = "18",

doi = "10.1145/2448496.2448510",

language = "English",

pages = "105--116",

booktitle = "Proceedings of the 16th International Conference on Database Theory",

publisher = "ACM",

note = "6th International Conference on Database Theory, ICDT 2013 ; Conference date: 18-03-2013 Through 22-03-2013",

url = "http://edbticdt2013.disi.unige.it/",

}

TY - GEN

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

AU - Björklund, Henrik

AU - Schuster, Martin

AU - Schwentick, Thomas

AU - Kulbatzki, Joscha

PY - 2013/3/18

Y1 - 2013/3/18

N2 - 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.

AB - 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.

U2 - 10.1145/2448496.2448510

DO - 10.1145/2448496.2448510

M3 - Conference contribution

SP - 105

EP - 116

BT - Proceedings of the 16th International Conference on Database Theory

PB - ACM

T2 - 6th International Conference on Database Theory

Y2 - 18 March 2013 through 22 March 2013

ER -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this