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

DOI10.2178/JSL/1344862160zbMATH Open1284.03136OpenAlexW2124322005MaRDI QIDQ2915891FDOQ2915891

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

equivalence relationsatisfiability problemfinite 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)

Cites Work

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

Cited In (9)

• Propositional epistemic logics with quantification over agents of knowledge (an alternative approach)
• Title not available (Why is that?)
• Small substructures and decidability issues for first-order logic with two variables
• The fluted fragment with transitive relations
• Epistemic logics with quantification over epistemic operators: decidability and expressiveness
• Metric propositional neighborhood logic with an equivalence relation
• A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic
• The Fluted Fragment with Transitivity
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable

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

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