Skip to Main content Skip to Navigation
New interface
Conference papers

Loops and Overloops for Tree Walking Automata

Pierre-Cyrille Heam 1, 2 Vincent Hugot 2 Olga Kouchnarenko 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 (UMR 6174), 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 tree overloops, which is closely related to tree loops, 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 transformation into a BUTA is slightly less straightforward than was 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.
Complete list of metadata
Contributor : Pierre-Cyrille Heam Connect in order to contact the contributor
Submitted on : Wednesday, November 16, 2011 - 3:24:20 PM
Last modification on : Friday, January 21, 2022 - 3:09:37 AM

Links full text



Pierre-Cyrille Heam, Vincent Hugot, Olga Kouchnarenko. Loops and Overloops for Tree Walking Automata. 16th International Conference on Implementation and Application of Automata - CIAA 2011, Jul 2011, Blois, France. pp.166-177, ⟨10.1007/978-3-642-22256-6_16⟩. ⟨hal-00641743⟩



Record views