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.
翻译:我们证明,对于每个正整数 k, 都存在一个 MSO_ 1 转换, 以最多 k 输出的线性分层图表示, 非决定性的, 宽度图受 k 函数约束的某种分层分解。 这一结果的直接推论是, CMSO_ 1- 可定义性和可识别性等同于线性线性分层图。