HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Residual Finite Tree Automata

Abstract : Tree automata based algorithms are essential in many fields in computer science such as verification, specification, program analysis. They become also essential for databases with the development of standards such as XML. In this paper, we define new classes of non deterministic tree automata, namely residual finite tree automata (RFTA). In the bottom-up case, we obtain a new characterization of regular tree languages. In the top-down case, we obtain a subclass of regular tree languages which contains the class of languages recognized by deterministic top-down tree automata. RFTA also come with the property of existence of canonical non deterministic tree automata.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

Contributor : Marc Tommasi Connect in order to contact the contributor
Submitted on : Tuesday, September 5, 2006 - 5:48:22 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:04 AM
Long-term archiving on: : Monday, September 20, 2010 - 4:53:06 PM





Julien Carme, Rémi Gilleron, Marc Tommasi, Alain Terlutte, Aurélien Lemay. Residual Finite Tree Automata. 7th International Conference on Developments in Language Theory, Jul 2003, Szeged, Hungary, Hungary. pp.171 -- 182. ⟨inria-00091272v2⟩



Record views


Files downloads