Complexity of Two-Variable Logic on Finite Trees

DOI10.1145/2996796zbMath1367.03062OpenAlexW2552825470MaRDI QIDQ5278193

Michael Benedikt, Saguy Benaim, Emanuel Kieroński, Witold Charatonik, Rastislav Lenhardt, Filip Mazowiecki, James Worrell

Publication date: 13 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:4a8207dd-6dad-4a13-a4cf-82ad51f6e822

zbMATH Keywords

treeslogic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Model theory of finite structures (03C13)

Related Items

Lifted inference with tree axioms, Unnamed Item, One-Dimensional Logic over Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Modal languages and bounded fragments of predicate logic
• The guarded fragment with transitive guards
• First-order logic with two variables and unary temporal logic
• Decidability of Downward XPath
• Two Variable vs. Linear Temporal Logic in Model Checking and Games
• Two-variable logic on data trees and XML reasoning
• XPath satisfiability in the presence of DTDs
• On the Decision Problem for Two-Variable First-Order Logic
• Decidability of weak logics with deterministic transitive closure
• On the Restraining Power of Guards
• Two-Variable Logic with Counting and Trees
• Complexity of Two-Variable Logic on Finite Trees
• Computer Science Logic
• Extending two-variable logic on data trees with order on data values and its automata