The two‐variable fragment with counting and equivalence
From MaRDI portal
Publication:3460527
DOI10.1002/malq.201400102zbMath1357.03040MaRDI QIDQ3460527
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
satisfiability; two-variable first-order logic; finite satisfiability; first-order logic with counting; NExpTime-completeness
68Q25: Analysis of algorithms and problem complexity
03B25: Decidability of theories and sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
03B20: Subsystems of classical logic (including intuitionistic logic)
Related Items
Regular Graphs and the Spectra of Two-Variable Logic with Counting, Two-Variable Logic with Counting and Trees, A Note on C² Interpreted over Finite Data-Words, Answering regular path queries mediated by unrestricted \(\mathcal{SQ}\) ontologies
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
