Complexity of two-variable logic on finite trees

DOI10.1145/2996796MaRDI QIDQ5278193zbMATH OpenOpenAlexWikidataFDO

Authors Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieroński, 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

logictrees

Mathematics Subject Classification ID

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

Recommendations

• Complexity of two-variable logic on finite trees
• Extending two-variable logic on trees
• On the Decision Problem for Two-Variable First-Order Logic
• Two-variable logic on data trees and XML reasoning
• Two-variable logic with counting and trees

Cites work

• \(\mathrm{FO}^2\) with one transitive relation is decidable
• Complexity of two-variable logic on finite trees
• Computer Science Logic
• Decidability of downward XPath
• Decidability of weak logics with deterministic transitive closure
• Extending two-variable logic on data trees with order on data values and its automata
• First-order logic with two variables and unary temporal logic
• scientific article; zbMATH DE number 2086420 (Why is no real title available?)
• Modal languages and bounded fragments of predicate logic
• On the Decision Problem for Two-Variable First-Order Logic
• On the Restraining Power of Guards
• The guarded fragment with transitive guards
• Two variable vs. linear temporal logic in model checking and games
• Two-variable logic on data trees and XML reasoning
• Two-variable logic with counting and trees
• XPath satisfiability in the presence of DTDs

Cited in

(19)

• First-order logic with two variables and unary temporal logic
• Deciding definability in \(\mathrm{FO}^2(<_{\mathbf{v}},<_{\mathbf{h}})\) on trees
• Two-variable logic on data trees and XML reasoning
• Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees
• Satisfiability of a Spatial Logic with Tree Variables
• Two-variable logic with a between relation
• Decidability and complexity of tree share formulas
• On the satisfiability of two-variable logic over data words
• scientific article; zbMATH DE number 1389856 (Why is no real title available?)
• Complexity Results for First-Order Two-Variable Logic with Counting
• Extending two-variable logic on trees
• One-Dimensional Logic over Trees
• Modulo counting on words and trees
• Complexity of two-variable logic on finite trees
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• Lifted inference with tree axioms
• A uniform one-dimensional fragment with alternation of quantifiers
• Alternating quantifiers in uniform one-dimensional fragments with an excursion into three-variable logic

This page was built for publication: Complexity of two-variable logic on finite trees

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