Reachability Problems for Controlled Rewriting Systems


Controlled rewriting is rewriting that specifies rewritable positions by
tree automata. It is more general than context-sensitive rewriting and
useful for expressing XML updates and so. I formalized it and proved
decidability and undecidability of reachability and regular model checking
for certain classes of controlled rewriting systems.