FO^2 with one transitive relation is decidable

DOI10.4230/LIPICS.STACS.2013.317MaRDI QIDQ2957894zbMATH OpenFDO

Authors Wiesław Szwast, Lidia Tendera

Publication date 30 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2013.317

zbMATH Keywords

classical decision problemcomputational complexitydecidabilitytwo-variable first-order logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• On the satisfiability problem for fragments of two-variable logic with one transitive relation
• Small substructures and decidability issues for first-order logic with two variables
• Decidability issues for two-variable logics with several linear orders
• Two-variable universal logic with transitive closure

Cited in

(10)

• Small substructures and decidability issues for first-order logic with two variables
• Two-Variable Separation Logic and Its Inner Circle
• A double team semantics for generalized quantifiers
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• On the satisfiability problem for fragments of two-variable logic with one transitive relation
• Regular graphs and the spectra of two-variable logic with counting
• On the decidability of elementary modal logics
• Two-variable logic with counting and trees
• Complexity of two-variable logic on finite trees
• On two-variable first-order logic with a partial order

This page was built for publication: \(\mathrm{FO}^2\) with one transitive relation is decidable

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