2006/09/05 by Julien Carme, J. Carme, Carme, J. +12
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #cs.CC #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0609015
arxiv created 2006/09/05 · openalex publication_date 2006/09/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.