We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic ( CMSO ) and have models of bounded treewidth, while target sentences express first-order logic ( FO ) properties. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes.

Fedor V. Fomin

Petr A. Golovach

Ignasi Sau

Giannos Stamoulis

Dimitrios M. Thilikos

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

Compound Logics for Modification Problems

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

Journal Info