An excursion to the border of decidability: between two- and three-variable logic

DOI10.29007/1XNSMaRDI QIDQ7025218zbMATH OpenFDO

Authors Oskar Fiuk, Emanuel Kieroński

Publication date 19 February 2025

Full work available at URL https://doi.org/10.29007/1XNS

zbMATH Keywords

finite satisfiability problemsatisfiability problemthree variable logictwo variable logicuniform one-dimensional fragment

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Many-valued logic (03B50) Complexity of computation (including implicit computational complexity) (03D15)

Cites work

• Complexity results for classes of quantificational formulas
• Computer Science Logic
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• One-dimensional fragment of first-order logic
• Random models and the Gödel case of the decision problem
• The unsolvability of the Gödel class with identity
• Unary negation
• Uniform one-dimensional fragments with one equivalence relation
• Zum Entscheidungsproblem des logischen Funktionenkalküls

Cited in

(2)

• A uniform one-dimensional fragment with alternation of quantifiers
• Alternating quantifiers in uniform one-dimensional fragments with an excursion into three-variable logic

This page was built for publication: An excursion to the border of decidability: between two- and three-variable logic

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