Logics with counting and equivalence

DOI10.1145/2603088.2603117MaRDI QIDQ4635661zbMATH OpenOpenAlexWikidataFDO

Authors Ian Pratt-Hartmann

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2603088.2603117

zbMATH Keywords

complexitysatisfiabilityequivalence relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25)

Recommendations

• The two-variable fragment with counting and equivalence
• Two-variable first-order logic with equivalence closure
• Two-variable first-order logic with equivalence closure
• Complexity Results for First-Order Two-Variable Logic with Counting
• Two-variable first-order logic with counting in forests

Cited in

(19)

• The two-variable fragment with counting and equivalence
• Two-variable first order logic with counting quantifiers: complexity results
• Second-order logic on equivalence relations
• Arrow logic and infinite counting
• On fixed-point logic with counting
• Graphs Identified by Logics with Counting
• Two-variable first-order logic with equivalence closure
• On logical and concurrent equivalences
• Graphs identified by logics with counting
• Two-variable logic with counting and a linear order
• Equivalence in finite-variable logics is complete for polynomial time
• Decidable logics with associative binary modalities
• The two-variable fragment with counting revisited
• A logical characterization of the counting hierarchy
• Modal Logics with Counting
• Two-variable first-order logic with counting in forests
• Weighted model counting beyond two-variable logic
• Two-variable first-order logic with equivalence closure
• Two-variable logic with counting and a linear order

This page was built for publication: Logics with counting and equivalence

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