Transitive closure logic, nested tree walking automata, and XPath

DOI10.1145/1706591.1706598zbMath1327.03024OpenAlexW2044007894MaRDI QIDQ3578193

Luc Segoufin, Balder ten Cate

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

tree automataXPathtransitive closure logic

Mathematics Subject Classification ID

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

Related Items (13)

Deciding twig-definability of node selecting tree automata ⋮ On the Hybrid Extension of CTL and CTL + ⋮ Capturing MSO with One Quantifier ⋮ Loops and overloops for tree-walking automata ⋮ Parametric random generation of deterministic tree automata ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees ⋮ Loops and Overloops for Tree Walking Automata ⋮ Random Generation of Deterministic Tree (Walking) Automata ⋮ On the Complexity of Branching-Time Logics ⋮ Automata on finite trees ⋮ Characterizing weighted MSO for trees by branching transitive closure logics

Uses Software

• XPath

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