Decidability issues for two-variable logics with several linear orders

DOI10.4230/LIPICS.CSL.2011.337MaRDI QIDQ2915693zbMATH OpenOpenAlexFDO

Authors Emanuel Kieroński

Publication date 18 September 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_777e.html

zbMATH Keywords

decidabilityguarded fragmentlinear orderstwo-variable logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25)

Recommendations

• Two-variable logic with two order relations (extended abstract)
• Two-variable logic with two order relations
• Two-variable logic with counting and a linear order
• Two variable first-order logic over ordered domains
• Two-variable logic on 2-dimensional structures

Cited in

(10)

• Two variable first-order logic over ordered domains
• \(\mathrm{FO}^2\) with one transitive relation is decidable
• Two-Variable Logic over Countable Linear Orderings
• Order-invariance of two-variable logic is decidable
• Undecidability results on two-variable logics
• \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
• Register automata with extrema constraints, and an application to two-variable logic
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• Two-variable logic with two order relations
• Two-variable logic with two order relations (extended abstract)

This page was built for publication: Decidability issues for two-variable logics with several linear orders

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