Name
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 context-free 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2448496.2448510 | international conference on database theory |
Keywords | DocType | Volume |
active xml,corresponding problem,active context-free game,optimum left-to-right strategy,rewritable string,target specification,left-to-right manner,input string,finite alphabet,finite replacement language,context-free game,conjunctive queries,computer science | Conference | abs/1212.3501 |
Citations | PageRank | References |
2 | 0.40 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henrik Björklund | 1 | 311 | 20.41 |
| Martin Schuster | 2 | 2 | 0.73 |
| Thomas Schwentick | 3 | 2373 | 155.10 |
| Joscha Kulbatzki | 4 | 2 | 0.40 |