Undecidability results on two-variable logics
From MaRDI portal
Publication:1306795
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
undecidabilitysatisfiabilitysatisfiability in finite modelsHilbert's \(\varepsilon\)-operatorfirst-order logic with two variablesmonadic fixed-point operationstransitive closure operationsweak access to cardinalities
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
