Undecidability results on two-variable logics

DOI10.1007/s001530050130zbMath0927.03015OpenAlexW2047674711MaRDI QIDQ1306795

Martin Otto, Erich Grädel, Eric Rosen

Publication date: 13 December 1999

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

Full work available at URL: https://doi.org/10.1007/s001530050130

zbMATH Keywords

undecidabilitysatisfiabilitysatisfiability in finite modelsHilbert's \(\varepsilon\)-operatorfirst-order logic with two variablesmonadic fixed-point operationstransitive closure operationsweak access to cardinalities

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25)

Related Items

Expressive Completeness of Separation Logic with Two Variables and No Separating Conjunction ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ A logic of reachable patterns in linked data-structures ⋮ On the Expressive Power of Query Languages for Matrices ⋮ Syllogistic Logic with “Most” ⋮ Separation logics and modalities: a survey ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Two-Variable Separation Logic and Its Inner Circle ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Syllogistic logic with comparative adjectives ⋮ Two variable first-order logic over ordered domains ⋮ Monadic Second-Order Logic and Transitive Closure Logics over Trees ⋮ One-variable logic meets Presburger arithmetic ⋮ Logics for Two Fragments beyond the Syllogistic Boundary ⋮ Unnamed Item ⋮ On the Restraining Power of Guards ⋮ On transitive modal many-valued logics ⋮ Guarded Negation ⋮ Guarded Negation