Small substructures and decidability issues for first-order logic with two variables

DOI10.2178/jsl/1344862160zbMath1284.03136OpenAlexW2124322005MaRDI QIDQ2915891

Martin Otto, Emanuel Kieroński

Publication date: 19 September 2012

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.jsl/1344862160

zbMATH Keywords

satisfiability problemequivalence relationfinite substructure propertylogic with two variablessmall substructure property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07)

Related Items (8)

Metric propositional neighborhood logic with an equivalence relation ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ Epistemic logics with quantification over epistemic operators: decidability and expressiveness ⋮ A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic ⋮ The fluted fragment with transitive relations ⋮ Unnamed Item ⋮ The Fluted Fragment with Transitivity ⋮ Propositional epistemic logics with quantification over agents of knowledge (an alternative approach)

Cites Work

• Unnamed Item
• On the complexity of the two-variable guarded fragment with transitive guards
• Modal languages and bounded fragments of predicate logic
• Undecidability results on two-variable logics
• On logics with two variables
• Carathéodory bounds for integer cones
• Remarks on Berger's paper on the domino problem
• Two variable first-order logic over ordered domains
• Small substructures and decidability issues for first-order logic with two variables
• On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards
• Two Variables and Two Successors
• The unsolvability of the Gödel class with identity
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• On the Satisfiability of Two-Variable Logic over Data Words
• On the Restraining Power of Guards
• Computer Science Logic
• The undecidability of the domino problem
• Two-Variable First-Order Logic with Equivalence Closure
• Two-Variable Logic with Two Order Relations

This page was built for publication: Small substructures and decidability issues for first-order logic with two variables