We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3 k +4) is a complete isomorphism test for the class of all graphs of rank width at most k . Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width k is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time n f(k) for a non-elementary function f . Our result yields an isomorphism test for graphs of rank width k running in time n O(k) . Another consequence of our result is the first polynomial-time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width.

Martin Grohe

Daniel Neuen

ACM Transactions on Computational Logic

TOCL 欢迎与计算机科学主题相关的逻辑各个方面的提交。该领域在计算机科学方面有着悠久的传统。获得 ACM 图灵奖的几位研究人员也为该领域做出了贡献，即 EDGAR CODD（关系数据库系统）、STEPHEN COOK（逻辑理论的复杂性）、EDSGER W. DIJKSTRA、ROBERT W. FLOYD、TONY HOARE、AMIR PNUELI、DANA SCOTT、EDMOND M. CLARKE、ALLEN E. EMERSON 和 JOSEPH SIFAKIS（程序逻辑、程序推导和验证、编程语言语义）、ROBIN MILNER（交互式定理证明、并发演算和函数式编程）和 JOHN MCCARTHY（函数式编程和人工智能中的逻辑）。逻辑在计算机科学中继续发挥重要作用，并已渗透到其多个领域，包括人工智能、计算复杂性、数据库系统和编程语言。本刊编委会寻求并希望吸引高- 在上述所有计算逻辑领域提交高质量的论文，使 TOCL 成为该领域的标准参考。理论和应用论文重新寻找。特别欢迎提交展示逻辑在计算机科学中的新颖使用的提交。

ACM Transactions on Computational Logic welcomes submissions on all aspects of logic related to computer science. This field has a long-standing tradition within computer science, with several Turing Award winners contributing significantly, including EDGAR CODD (relational database systems), STEPHEN COOK (complexity of logical theories), EDSGER W. DIJKSTRA, ROBERT W. FLOYD, TONY HOARE, AMIR PNUELI, DANA SCOTT, EDMOND M. CLARKE, ALLEN E. EMERSON, and JOSEPH SIFAKIS (program logic, program derivation and verification, semantics of programming languages), ROBIN MILNER (interactive theorem proving, concurrent calculi, and functional programming), and JOHN MCCARTHY (logic in functional programming and artificial intelligence). Logic continues to play a vital role in computer science and has permeated various fields, including artificial intelligence, computational complexity, database systems, and programming languages. The editorial board seeks to attract high-quality submissions in all areas of computational logic, aiming to make ACM Transactions on Computational Logic a standard reference in the field. We particularly welcome submissions that showcase novel uses of logic in computer science.

《ACM Transactions on Computational Logic》欢迎与计算机科学相关的逻辑各个方面的投稿。该领域在计算机科学中有着悠久的传统，许多获得ACM图灵奖的研究人员对其做出了重要贡献，包括EDGAR CODD（关系数据库系统）、STEPHEN COOK（逻辑理论的复杂性）、EDSGER W. DIJKSTRA、ROBERT W. FLOYD、TONY HOARE、AMIR PNUELI、DANA SCOTT、EDMOND M. CLARKE、ALLEN E. EMERSON和JOSEPH SIFAKIS（程序逻辑、程序推导和验证、编程语言语义）、ROBIN MILNER（交互式定理证明、并发演算和函数式编程）以及JOHN MCCARTHY（函数式编程和人工智能中的逻辑）。逻辑在计算机科学中继续发挥着重要作用，并已渗透到多个领域，包括人工智能、计算复杂性、数据库系统和编程语言。本刊编委会希望吸引在上述所有计算逻辑领域提交高质量论文，使《ACM Transactions on Computational Logic》成为该领域的标准参考。我们欢迎理论和应用论文的投稿，特别是那些展示逻辑在计算机科学中新颖应用的研究。

Category	Quartile
数学	4
数学, 计算机理论方法	4
数学, 逻辑学	4

Canonisation and Definability for Graphs of Bounded Rank Width

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info