Two-Variable Logic with Counting and Trees

DOI10.1145/2983622zbMath1367.03063OpenAlexW2549023517MaRDI QIDQ5278191

Piotr Witkowski, Witold Charatonik

Publication date: 13 July 2017

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

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

zbMATH Keywords

treesatisfiabilitytwo-variable logiccounting quantifier

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13)

Cites Work

• Unnamed Item
• Elements of finite model theory.
• Carathéodory bounds for integer cones
• First-order logic with two variables and unary temporal logic
• Complexity of the two-variable fragment with counting quantifiers
• Two variable first-order logic over ordered domains
• Two-variable logic on data trees and XML reasoning
• The two‐variable fragment with counting and equivalence
• How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited
• Two Variables and Two Successors
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• Two-Variable Universal Logic with Transitive Closure
• The Two-Variable Fragment with Counting Revisited
• On the Complexity of the Bernays-Schönfinkel Class with Datalog
• Reachability Problems in Vector Addition Systems
• Two-Variable Logic with Counting and Trees
• Complexity of Two-Variable Logic on Finite Trees
• Computer Science Logic
• STACS 2005
• Two-variable Logic with Counting and a Linear Order
• Two-Variable First-Order Logic with Equivalence Closure
• Two-Variable Logic with Two Order Relations