Loops and overloops for Tree Walking Automata

Pierre-Cyrille Heam 1, 2 Vincent Hugot 1, 2 Olga Kouchnarenko 1, 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Tree-Walking Automata (TWA) have lately received renewed interest thanks to their tight connection to XML. This paper introduces the notion of treeoverloops, which is closely related to treeloops, and investigates the use of both for the following common operations on TWA: testing membership, transformation into a Bottom-Up Tree Automaton (BUTA), and testing emptiness. Notably, we argue that the transformation into a BUTA is slightly less straightforward than was previously assumed, show that using overloops yields much smaller BUTA in the deterministic case, and provide a polynomial over-approximation of this construction which detects emptiness with surprising accuracy against randomly generated TWA.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, Implementation and Application of Automata (CIAA 2011), 450, pp.43-53. 〈http://www.sciencedirect.com/science/article/pii/S0304397512003817〉. 〈10.1016/j.tcs.2012.04.026〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00756514
Contributeur : Pierre-Cyrille Heam <>
Soumis le : vendredi 23 novembre 2012 - 10:56:18
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Lien texte intégral

Identifiants

Citation

Pierre-Cyrille Heam, Vincent Hugot, Olga Kouchnarenko. Loops and overloops for Tree Walking Automata. Theoretical Computer Science, Elsevier, 2012, Implementation and Application of Automata (CIAA 2011), 450, pp.43-53. 〈http://www.sciencedirect.com/science/article/pii/S0304397512003817〉. 〈10.1016/j.tcs.2012.04.026〉. 〈hal-00756514〉

Partager

Métriques

Consultations de la notice

213