Computational complexity of theories of a binary predicate with a small number of variables

DOI10.1134/S1064562422700053MaRDI QIDQ2696689

Yanyan Li

Publication date: 17 April 2023

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

undecidabilityfirst-order logicdyadic logicChurch's theoremTrakhtenbrot's theorem

Mathematics Subject Classification ID

General logic (03Bxx) Computability and recursion theory (03Dxx)

Cites Work

• Deterministic aperiodic tile sets
• Undecidability results on two-variable logics
• Tiling with polyominoes and combinatorial group theory
• Undecidable fragments of elementary theories
• A note on hereditarily Π10- and Σ10-complete sets of sentences
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Algorithmic properties of first-order modal logics of linear Kripke frames in restricted languages
• Computability and Logic
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• On the complexity of propositional quantification in intuitionistic logic
• On the Products of Linear Modal Logics
• On the Restraining Power of Guards
• Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
• The undecidability of the domino problem
• Impossibility of an algorithm for the decision problem in finite classes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computational complexity of theories of a binary predicate with a small number of variables