FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, 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.
7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. Springer, 2013, Lecture Notes in Computer Science
https://hal.inria.fr/hal-00767719
Contributeur : Florent Jacquemard
<>
Soumis le : jeudi 20 décembre 2012 - 16:25:21
Dernière modification le : mardi 17 avril 2018 - 11:30:05
Document(s) archivé(s) le : jeudi 21 mars 2013 - 03:49:04
Florent Jacquemard, Michael Rusinowitch. Rewrite Closure and CF Hedge Automata. 7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. Springer, 2013, Lecture Notes in Computer Science. 〈hal-00767719〉