Rewrite Closure and CF Hedge Automata
  We introduce an extension of hedge automata called bidimensional context-free hedge automata. The class of unranked ordered tree languages they recognize is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages. 
Florent Jacquemard (Inria Paris-Rocquencourt, STMS), Michael   Rusinowitch (INRIA Lorraine - LORIA / LIFC)
cs.LO cs.DB cs.FL