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- 可定义性和可识别性等同于线性线性分层图。

0
下载
关闭预览

相关内容

【DeepMind】强化学习教程,83页ppt
专知会员服务
158+阅读 · 2020年8月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
112+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月15日
VIP会员
相关VIP内容
【DeepMind】强化学习教程,83页ppt
专知会员服务
158+阅读 · 2020年8月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
112+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员