Revision as of 13:51, 9 May 2022 edit Felix QW (talk \| contribs) Extended confirmed users 8,596 edits Removed ref-improve (everything cited) Tag: 2017 wikitext editor ← Previous edit		Latest revision as of 13:07, 13 September 2022 edit undo Storchy (talk \| contribs) Extended confirmed users 35,151 edits →Connection to the Weisfeiler-Leman algorithm
Line 15: == Connection to the Weisfeiler-Leman algorithm == There is a strong connection between two-variable logic and the Weisfeiler-Leman (or [[Colour refinement algorithm\|color refinement]]) algorithm. Given two graphs, then any two nodes have the same stable color in color refinement if and only if they have the same <math>C^2</math> type, that is, they satisfy the same formulas in two-variable logic with counting.<ref>Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.</ref> == References ==

Two-variable logic: Difference between revisions