Two-variable Logic with Counting and a Linear Order

DOI10.4230/LIPIcs.CSL.2015.631zbMath1373.68259arXiv1604.06038OpenAlexW2964257511MaRDI QIDQ5351987

Witold Charatonik, Piotr Witkowski

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1604.06038

zbMATH Keywords

complexitysatisfiabilitylinear ordertwo-variable logiccounting quantifiers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20) Descriptive complexity and finite models (68Q19)

Related Items (2)

Unnamed Item ⋮ One-Dimensional Logic over Trees

This page was built for publication: Two-variable Logic with Counting and a Linear Order