The two‐variable fragment with counting and equivalence

DOI10.1002/malq.201400102zbMath1357.03040OpenAlexW2189181601MaRDI QIDQ3460527

Ian Pratt-Hartmann

Publication date: 7 January 2016

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.201400102

zbMATH Keywords

satisfiabilitytwo-variable first-order logicfinite satisfiabilityfirst-order logic with countingNExpTime-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (4)

Two-Variable Logic with Counting and Trees ⋮ Answering regular path queries mediated by unrestricted \(\mathcal{SQ}\) ontologies ⋮ A Note on C² Interpreted over Finite Data-Words ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting

Cites Work

• Small solutions of linear diophantine equations
• Modal languages and bounded fragments of predicate logic
• A tableau decision procedure for \(\mathcal{SHOIQ}\)
• Carathéodory bounds for integer cones
• Complexity of the two-variable fragment with counting quantifiers
• Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
• On the complexity of integer programming
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• Practical reasoning for very expressive description logics
• On the Restraining Power of Guards
• STACS 2005
• Undecidability of some simple formalized theories
• Two-Variable First-Order Logic with Equivalence Closure

This page was built for publication: The two‐variable fragment with counting and equivalence