Revision as of 07:19, 14 May 2020 edit Martinalex000 (talk \| contribs) 33 edits added a small section on the WL algorithm (more to come) Tag: Visual edit: Switched ← Previous edit		Revision as of 07:21, 14 May 2020 edit undo Martinalex000 (talk \| contribs) 33 edits m →Connection to the Weisfeiler-Leman algorithm Next edit →
Line 14: == Connection to the Weisfeiler-Leman algorithm == There is a strong connection between two-variable logic and the Weisfeiler-Leman (or 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