Complexity of two-variable logic on finite trees

DOI10.1007/978-3-642-39212-2_10MaRDI QIDQ5327424zbMATH OpenOpenAlexFDO

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

Publication date 7 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

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

Cited in

(13)

• Two-Variable Separation Logic and Its Inner Circle
• A double team semantics for generalized quantifiers
• Deciding definability in \(\mathrm{FO}^2(<_{\mathbf{v}},<_{\mathbf{h}})\) on trees
• Two-variable logic on data trees and XML reasoning
• 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
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• Extending two-variable logic on trees
• Two-variable logic with counting and trees
• Complexity of two-variable logic on finite trees

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 Q5327424)