Two-variable logic with counting and trees

DOI10.1145/2983622MaRDI QIDQ5278191zbMATH OpenOpenAlexWikidataFDO

Authors Witold Charatonik, Piotr Witkowski

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

counting quantifiersatisfiabilitytreetwo-variable logic

Mathematics Subject Classification ID

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

Recommendations

• Two-variable logic with counting and trees
• Two-variable first-order logic with counting in forests
• Extending two-variable logic on trees
• Two-variable logic with counting and a linear order
• Two-variable logic with counting and a linear order

Cites work

• \(\mathrm{FO}^2\) with one transitive relation is decidable
• Carathéodory bounds for integer cones
• Complexity of the two-variable fragment with counting quantifiers
• Complexity of two-variable logic on finite trees
• Computer Science Logic
• Elements of finite model theory.
• First-order logic with two variables and unary temporal logic
• How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited
• On languages with two variables
• On the complexity of the Bernays-Schönfinkel class with Datalog
• On the Decision Problem for Two-Variable First-Order Logic
• Reachability Problems in Vector Addition Systems
• STACS 2005
• The two-variable fragment with counting and equivalence
• The two-variable fragment with counting revisited
• Two variable first-order logic over ordered domains
• Two variables and two successors
• Two-variable first-order logic with equivalence closure
• Two-variable logic on data trees and XML reasoning
• Two-variable logic with counting and a linear order
• Two-variable logic with counting and trees
• Two-variable logic with two order relations (extended abstract)
• Two-variable universal logic with transitive closure

Cited in

(8)

• The two-variable fragment with counting revisited
• Extending two-variable logic on trees
• Modulo counting on words and trees
• Two-variable first-order logic with counting in forests
• Two-variable logic with counting and trees
• Two variable logic with ultimately periodic counting
• Two variable logic with ultimately periodic counting
• Alternating quantifiers in uniform one-dimensional fragments with an excursion into three-variable logic

This page was built for publication: Two-variable logic with counting and trees

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