Rewrite Closure and CF Hedge Automata

abstract: 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.

Recommended citation: Florent Jacquemard, Michael Rusinowitch, "Rewrite Closure and CF Hedge Automata" In the proceedings of 7th International Conference on Language and Automata Theory and Application, Springer LNCS 7810, 2013.