一句话：证明 MSO_1 转导可从有界线性团宽度图非确定输出有界团宽度分解，并推出 CMSO_1 可定义性与可识别性等价。
本文研究有界线性团宽度图上的可定义分解问题。作者证明，对每个正整数 k，存在一个 MSO_1 转导：给定线性团宽度不超过 k 的图，它能非确定地输出该图的某个团宽度分解，且输出分解的宽度仅受 k 的某个函数限制。这表明有界线性团宽度图的团宽度分解可以在 MSO_1 逻辑中可定义地获得。作为直接推论，在有界线性团宽度图上，CMSO_1 可定义性与可识别性等价。该结果直接建立了逻辑可定义性与可识别性之间的等价关系，并给出了有界线性团宽度图的一种可定义结构分解。
We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of CMSO_1-definability and recognizability on graphs of bounded linear cliquewidth.
@article{paperbot1346,
title = {Definable decompositions for graphs of bounded linear cliquewidth},
author = {Mikołaj Bojańczyk and Martin Grohe and Michał Pilipczuk},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 1},
year = {2021},
doi = {10.23638/lmcs-17(1:5)2021}
}