Two-Variable First-Order Logic with Equivalence Closure

DOI10.1137/120900095zbMath1341.03014OpenAlexW2027602125MaRDI QIDQ5895185

Ian Pratt-Hartmann, Lidia Tendera, Emanuel Kieroński, Jakub Michaliszyn

Publication date: 18 September 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120900095

zbMATH Keywords

computational complexitydecidability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (9)

Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\) ⋮ The two‐variable fragment with counting and equivalence ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ The Support of Integer Optimal Solutions ⋮ Epistemic logics with quantification over epistemic operators: decidability and expressiveness ⋮ Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable ⋮ The fluted fragment with transitive relations ⋮ The Fluted Fragment with Transitivity ⋮ Propositional epistemic logics with quantification over agents of knowledge (an alternative approach)

This page was built for publication: Two-Variable First-Order Logic with Equivalence Closure