Two-Variable Logic over Countable Linear Orderings

DOI10.4230/LIPICS.MFCS.2016.66zbMATH Open1398.03063OpenAlexW2541640833MaRDI QIDQ4608629FDOQ4608629

Authors: Amaldev Manuel, A. V. Sreejith 

Publication date: 21 March 2018

Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2016.html#ManuelS16

Recommendations

• Two-variable logic with counting and a linear order
• Two-variable logic with counting and a linear order
• Two-variable logic with two order relations (extended abstract)
• Two variable first-order logic over ordered domains
• Decidability issues for two-variable logics with several linear orders
• Two-variable logic with two order relations
• Two-variable first order logic with counting quantifiers: complexity results
• Order-invariance of two-variable logic is decidable
• Complexity Results for First-Order Two-Variable Logic with Counting
• On logics with two variables

zbMATH Keywords

countable linear orderings\(\circ\)-monoids\(\mathrm{FO}^2\)

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Abstract data types; algebraic specification (68Q65)

Cited In (12)

• Linear circuits, two-variable logic and weakly blocked monoids
• Two-variable logic with counting and a linear order
• Complexity Results for First-Order Two-Variable Logic with Counting
• Limited set quantifiers over countable linear orderings
• An algebraic approach to MSO-definability on countable linear orderings
• First-order logic and its infinitary quantifier extensions over countable words
• First-order separation over countable ordinals
• Two-variable logic with counting and a linear order
• Existential MSO over two successors is strictly weaker than over linear orders
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic

This page was built for publication: Two-Variable Logic over Countable Linear Orderings

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