The Power of Counting Logics on Restricted Classes of Finite Structures

DOI10.1007/978-3-540-74915-8_10MaRDI QIDQ3608406zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, David Richerby

Publication date 5 March 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74915-8_10

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Graph minors (05C83) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• The expressive power of fixed-point logic with counting
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• On fixed-point logic with counting
• On the expressive power of counting
• Logics with counting and local properties

Cited in

(18)

• Lower bounds for invariant queries in logics with counting.
• Countably many weakenings of Belnap-Dunn logic
• On fixed-point logic with counting
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• Benchmark Graphs for Practical Graph Isomorphism
• A logical characterization of the counting hierarchy
• CFI Construction and Balanced Graphs
• Symmetric arithmetic circuits
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Symmetric arithmetic circuits
• Homomorphism-distinguishing closedness for graphs of bounded tree-width
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Bounding the Weisfeiler-Leman dimension via a depth analysis of I/R-trees
• Computational complexity of the Weisfeiler-Leman dimension
• Finite variable counting logics with restricted requantification
• Computational complexity of the Weisfeiler-Leman dimension
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

This page was built for publication: The Power of Counting Logics on Restricted Classes of Finite Structures

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