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
下载
关闭预览

相关内容

【Google】梯度下降,48页ppt
专知会员服务
79+阅读 · 2020年12月5日
【DeepMind】强化学习教程,83页ppt
专知会员服务
149+阅读 · 2020年8月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
240+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
169+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
已删除
将门创投
5+阅读 · 2017年11月20日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
手把手教你用LDA特征选择
AI研习社
12+阅读 · 2017年8月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月15日
VIP会员
相关VIP内容
【Google】梯度下降,48页ppt
专知会员服务
79+阅读 · 2020年12月5日
【DeepMind】强化学习教程,83页ppt
专知会员服务
149+阅读 · 2020年8月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
240+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
169+阅读 · 2019年10月11日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
已删除
将门创投
5+阅读 · 2017年11月20日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
手把手教你用LDA特征选择
AI研习社
12+阅读 · 2017年8月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员