文章基本信息

标题：Definable decompositions for graphs of bounded linear cliquewidth
本地全文：下载
作者：Pilipczuk, Michał ; Grohe, Martin ; Bojańczyk, Mikołaj 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2021
卷号：17
期号：1
页码：1-40
语种：English
出版社：Technical University of Braunschweig
摘要：We prove that for every positive integer k, there exists anMSO_1-transduction that given a graph of linear cliquewidth at most k outputs,nondeterministically, some cliquewidth decomposition of the graph of widthbounded by a function of k. A direct corollary of this result is theequivalence of the notions of CMSO_1-definability and recognizability on graphsof bounded linear cliquewidth.
关键词：Computer Science - Logic in Computer Science