Two-variable Logic with Counting and a Linear Order

DOI10.2168/LMCS-12(2:8)2016zbMath1448.03006MaRDI QIDQ5739893

Witold Charatonik, Piotr Witkowski

Publication date: 6 July 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexitysatisfiabilitylinear ordertwo-variable logiccounting quantifiers

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20) Descriptive complexity and finite models (68Q19)

Related Items (3)

Two-Variable Logic with Counting and Trees ⋮ ``Most of leads to undecidability: failure of adding frequencies to LTL ⋮ A Note on C² Interpreted over Finite Data-Words

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