On Optimum Left-to-Right Strategies for Active Context-Free Games

Date Added: Dec 2012
Format: PDF

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 un-decidable 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.