Undecidability results on two-variable logics

DOI10.1007/S001530050130MaRDI QIDQ1306795zbMATH OpenOpenAlexFDO

Authors Erich Grädel, Martin Otto, 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

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

Mathematics Subject Classification ID

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

Recommendations

• Undecidability results on two-variable logics
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Undecidability of modal and intermediate first-order logics with two individual variables
• Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Undecidability of propositional separation logic and its neighbours
• Undecidable properties of extensions of provability logic. II
• The undecidability of second order multiplicative linear logic
• scientific article; zbMATH DE number 1114339
• Undecidable properties of extensions of the logic of provability
• Undecidability of multiplicative subexponential logic

Cited in

(27)

• Undecidability of modal and intermediate first-order logics with two individual variables
• Syllogistic logic with ``most
• Small substructures and decidability issues for first-order logic with two variables
• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• Guarded negation
• Two variable logic with ultimately periodic counting
• Separation logics and modalities: a survey
• scientific article; zbMATH DE number 7561661 (Why is no real title available?)
• On the Restraining Power of Guards
• One-variable logic meets Presburger arithmetic
• Syllogistic logic with comparative adjectives
• Expressive completeness of separation logic with two variables and no separating conjunction
• On the expressive power of query languages for matrices
• On transitive modal many-valued logics
• Two-Variable Separation Logic and Its Inner Circle
• Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?
• Undecidability results on two-variable logics
• Computational complexity of theories of a binary predicate with a small number of variables
• Two results in negation-free logic
• Logics for two fragments beyond the syllogistic boundary
• INTERLEAVING LOGIC AND COUNTING
• On logics with two variables
• Guarded negation
• Two variable first-order logic over ordered domains
• A logic of reachable patterns in linked data-structures
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Undecidable first-order theories of affine geometries

This page was built for publication: Undecidability results on two-variable logics

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