Two-variable logic with counting and a linear order

DOI10.2168/LMCS-12(2:8)2016MaRDI QIDQ5739893zbMATH OpenFDO

Authors Witold Charatonik, Piotr Witkowski

Publication date 6 July 2016

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

Full work available at URL https://doi.org/10.2168/LMCS-12(2:8)2016

zbMATH Keywords

complexitycounting quantifierslinear ordersatisfiabilitytwo-variable logic

Mathematics Subject Classification ID

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

Recommendations

• Two-variable logic with counting and a linear order
• Two-Variable Logic over Countable Linear Orderings
• The two-variable fragment with counting and equivalence
• Logics with counting and equivalence
• Two-variable first order logic with counting quantifiers: complexity results

Cited in

(12)

• ``Most of leads to undecidability: failure of adding frequencies to LTL
• Data-complexity of the two-variable fragment with counting quantifiers
• Two-Variable Logic over Countable Linear Orderings
• Register automata with extrema constraints, and an application to two-variable logic
• Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
• Two-variable logic with counting and trees
• Two-variable logic with counting and trees
• Two-variable logic with counting and a linear order
• A Note on C² Interpreted over Finite Data-Words
• Two variable logic with ultimately periodic counting
• About the expressive power and complexity of order-invariance with two variables
• Alternating quantifiers in uniform one-dimensional fragments with an excursion into three-variable logic

This page was built for publication: Two-variable logic with counting and a linear order

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