On optimum left-to-right strategies for active context-free gamesReportar como inadecuado



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


On optimum left-to-right strategies for active context-free games - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: 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.



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

Fuente: https://archive.org/







Documentos relacionados