FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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.
https://hal.inria.fr/hal-00767719
Contributor : Florent Jacquemard
<>
Submitted on : Thursday, December 20, 2012 - 4:25:21 PM
Last modification on : Saturday, March 30, 2019 - 1:26:31 AM
Long-term archiving on : Thursday, March 21, 2013 - 3:49:04 AM
Florent Jacquemard, Michael Rusinowitch. Rewrite Closure and CF Hedge Automata. 7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. ⟨hal-00767719⟩
