2006/06/30 by Leonid Libkin · 1 citation
Computer Science · Mathematics · #Advanced Database Systems and Queries #Automaton #Combinatorics #Computer science #Formal Methods in Verification #Mathematics #Theoretical computer science #Tree (set theory) #Tree automaton #World Wide Web #XML #cs.DB #cs.LO #semigroups and automata theory
paper · pdf · doi:10.2168/lmcs-2(3:2)2006
published as Logical Methods in Computer Science, Volume 2, Issue 3 (July 26, 2006) lmcs:2244
arxiv created 2006/07/26 · openalex publication_date 2006/07/26 · arxiv updated 2017/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to relate complex properties of trees to the existence of tree automata for those properties. Furthermore, logics differ significantly in their model-checking properties, their automata models, and their behavior on ordered and unordered trees. In this paper we present a survey of logics for unranked trees.