Transitive closure logic, nested tree walking automata, and XPath

DOI10.1145/1706591.1706598MaRDI QIDQ3578193zbMATH OpenOpenAlexFDO

Authors Balder ten Cate, Luc Segoufin

Publication date 14 July 2010

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1706591.1706598

zbMATH Keywords

transitive closure logictree automataXPath

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the power of tree-walking automata.
• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• scientific article; zbMATH DE number 1670851
• The complexity of query containment in expressive fragments of XPath 2.0
• Monadic Second-Order Logic and Transitive Closure Logics over Trees

Cited in

(19)

• Parametric random generation of deterministic tree automata
• Automata on finite trees
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• Characterizing weighted MSO for trees by branching transitive closure logics
• Model theory of XPath on data trees. II: Binary bisimulation and definability
• Deciding twig-definability of node selecting tree automata
• Capturing MSO with one quantifier
• scientific article; zbMATH DE number 5999538 (Why is no real title available?)
• On the Hybrid Extension of CTL and CTL +
• Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees
• Random Generation of Deterministic Tree (Walking) Automata
• On the Complexity of Branching-Time Logics
• Loops and overloops for tree-walking automata
• Pebble weighted automata and weighted logics
• Loops and overloops for tree walking automata
• Limiting Until in ordered tree query languages
• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• Subshifts defined by nondeterministic and alternating plane-walking automata
• XML schema, tree logic and sheaves automata

Describes a project that uses

Uses Software

• XPath

This page was built for publication: Transitive closure logic, nested tree walking automata, and XPath

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3578193)