会员服务
2021 年 4 月 27 日
The Reachability Problem for Petri Nets is Not Primitive Recursive
翻译：Petri Nets的可获取性问题不是原始递归问题
Jérôme Leroux
Jérôme Leroux
from arxiv, A beautiful and much simpler proof from Wojciech Czerwi\'nski and {\L}ukasz Orlikowski will soon be available on arXiv

We present a way to lift up the tower lowerbound of the reachability problem for Petri nets to match the Ackermannian upperbound closing a long standing open problem. We also prove that the reachability problem in fix dimension is not elementary.


翻译：我们提出一种方法来提升Petri网可达性问题的低端塔塔,以配合阿克曼人顶端的Ackermannian上层封闭一个长期存在的未决问题。 我们还证明固定层面的可达性问题不是最基本的问题。
0
下载
关闭预览

相关内容

【南京大学】量子计算 (Spring 2021)课程
专知会员服务
56+阅读 · 2021年4月12日
【ICLR2021】神经元注意力蒸馏消除DNN中的后门触发器
【ICLR2021】神经元注意力蒸馏消除DNN中的后门触发器
专知会员服务
13+阅读 · 2021年1月31日
NLP必读经典文献100篇
专知会员服务
123+阅读 · 2020年9月8日
2020数据工程师成长路线图
专知会员服务
39+阅读 · 2020年9月6日
【机器推理可解释性】Machine Reasoning Explainability
【机器推理可解释性】Machine Reasoning Explainability
专知会员服务
34+阅读 · 2020年9月3日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
双目深度估计中的自监督学习概览
双目深度估计中的自监督学习概览
PaperWeekly
7+阅读 · 2020年3月5日
【TED】生命中的每一年的智慧
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
五个精彩实用的自然语言处理资源
五个精彩实用的自然语言处理资源
机器学习研究会
6+阅读 · 2018年2月23日
基于LSTM-CNN组合模型的Twitter情感分析（附代码）
基于LSTM-CNN组合模型的Twitter情感分析（附代码）
机器学习研究会
50+阅读 · 2018年2月21日
Capsule Networks解析
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
python文本相似度计算
python文本相似度计算
北京思腾合力科技有限公司
24+阅读 · 2017年11月6日
【推荐】RNN/LSTM时序预测
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Efficient Computation of Sequence Mappability
Arxiv
0+阅读 · 2021年6月16日
Counterfactual Explanations as Interventions in Latent Space
Arxiv
0+阅读 · 2021年6月14日
Distributionally Robust Martingale Optimal Transport
Arxiv
0+阅读 · 2021年6月14日
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
Arxiv
0+阅读 · 2021年6月13日
Complexity of Linear Minimization and Projection on Some Sets
Arxiv
0+阅读 · 2021年6月12日
Separations for Estimating Large Frequency Moments on Data Streams
Arxiv
0+阅读 · 2021年6月11日
Numerical Solution of the $L^1$-Optimal Transport Problem on Surfaces
Numerical Solution of the $L^1$-Optimal Transport Problem on Surfaces
Arxiv
0+阅读 · 2021年6月11日
A proof of P!=NP
Arxiv
0+阅读 · 2021年4月2日
Reachability in arborescence packings
Arxiv
0+阅读 · 2020年6月29日
Physical Primitive Decomposition
Physical Primitive Decomposition
Arxiv
4+阅读 · 2018年9月13日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
相关VIP内容
【南京大学】量子计算 (Spring 2021)课程
专知会员服务
56+阅读 · 2021年4月12日
【ICLR2021】神经元注意力蒸馏消除DNN中的后门触发器
【ICLR2021】神经元注意力蒸馏消除DNN中的后门触发器
专知会员服务
13+阅读 · 2021年1月31日
NLP必读经典文献100篇
专知会员服务
123+阅读 · 2020年9月8日
2020数据工程师成长路线图
专知会员服务
39+阅读 · 2020年9月6日
【机器推理可解释性】Machine Reasoning Explainability
【机器推理可解释性】Machine Reasoning Explainability
专知会员服务
34+阅读 · 2020年9月3日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
热门VIP内容
相关资讯
双目深度估计中的自监督学习概览
双目深度估计中的自监督学习概览
PaperWeekly
7+阅读 · 2020年3月5日
【TED】生命中的每一年的智慧
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
五个精彩实用的自然语言处理资源
五个精彩实用的自然语言处理资源
机器学习研究会
6+阅读 · 2018年2月23日
基于LSTM-CNN组合模型的Twitter情感分析（附代码）
基于LSTM-CNN组合模型的Twitter情感分析（附代码）
机器学习研究会
50+阅读 · 2018年2月21日
Capsule Networks解析
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
python文本相似度计算
python文本相似度计算
北京思腾合力科技有限公司
24+阅读 · 2017年11月6日
【推荐】RNN/LSTM时序预测
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关论文
Efficient Computation of Sequence Mappability
Arxiv
0+阅读 · 2021年6月16日
Counterfactual Explanations as Interventions in Latent Space
Arxiv
0+阅读 · 2021年6月14日
Distributionally Robust Martingale Optimal Transport
Arxiv
0+阅读 · 2021年6月14日
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
Arxiv
0+阅读 · 2021年6月13日
Complexity of Linear Minimization and Projection on Some Sets
Arxiv
0+阅读 · 2021年6月12日
Separations for Estimating Large Frequency Moments on Data Streams
Arxiv
0+阅读 · 2021年6月11日
Numerical Solution of the $L^1$-Optimal Transport Problem on Surfaces
Numerical Solution of the $L^1$-Optimal Transport Problem on Surfaces
Arxiv
0+阅读 · 2021年6月11日
A proof of P!=NP
Arxiv
0+阅读 · 2021年4月2日
Reachability in arborescence packings
Arxiv
0+阅读 · 2020年6月29日
Physical Primitive Decomposition
Physical Primitive Decomposition
Arxiv
4+阅读 · 2018年9月13日
Top
微信扫码咨询专知VIP会员
Top