Query automata over finite trees

DOI10.1016/S0304-3975(01)00301-2zbMath1026.68081MaRDI QIDQ1607226

Frank Neven, Thomas Schwentick

Publication date: 31 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

XMLquery languagesformal languageslogictree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

Deciding twig-definability of node selecting tree automata ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Controlled Term Rewriting ⋮ Query Automata for Nested Words ⋮ XML schema, tree logic and sheaves automata ⋮ Visibly pushdown transducers ⋮ Automata for XML -- a survey ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ One-variable context-free hedge automata ⋮ Weighted logics for unranked tree automata ⋮ Regular languages of nested words: fixed points, automata, and synchronization ⋮ Weighted monadic Datalog ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Reasoning about XML with temporal logics and automata ⋮ On the complexity of typechecking top-down XML transformations ⋮ Attribute grammars for unranked trees as a query language for structured documents ⋮ Document Spanners ⋮ Tree Automata over Infinite Alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On two-way tree automata
• Complexity results for two-way and multi-pebble automata and their logics
• Domino-tiling games
• Tree acceptors and some of their applications
• Expressiveness of structured document query languages based on attribute grammars
• Weak Second‐Order Arithmetic and Finite Automata
• Generalizations of regular sets and their application to a study of context-free languages
• Application of model theoretic games to discrete linear orders and finite automata
• A Grammar-Based Approach Towards Unifying Hierarchical Data Models
• MSO definable string transductions and two-way finite-state transducers
• Numeration systems, linear recurrences, and regular sets
• An Approach to a Unified Theory of Automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A general theory of translation
• Définition et etude des Bilangages réguliers

This page was built for publication: Query automata over finite trees