On optimum left-to-right strategies for active context-free gamesReport as inadecuate



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


On optimum left-to-right strategies for active context-free games - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: On optimum left-to-right strategies for active context-free games
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.



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

Source: https://archive.org/







Related documents