会员服务
2021 年 6 月 4 日
The Reachability Problem for Petri Nets is Not Primitive Recursive
翻译：Petri Nets的可获取性问题不是原始递归问题
Jérôme Leroux
Jérôme Leroux
from arxiv, Version submitted to FOCS 2021

We present a way to lift up the Tower complexity lower bound of the reachability problem for Petri nets to match the Ackermannian upper bound closing a long standing open problem. We also prove that the reachability problem in dimension 17 is not elementary.


翻译：我们提出一种方法来提升塔的复杂程度,降低Petrii 网的可达性问题下限,以便与阿克曼人上界的可达性匹配,解决一个长期存在的开放问题。 我们还证明,第17维的可达性问题不是最基本的问题。
0
下载
关闭预览

相关内容

【图神经网络导论】Intro to Graph Neural Networks，176页ppt
【图神经网络导论】Intro to Graph Neural Networks，176页ppt
专知会员服务
123+阅读 · 2021年6月4日
【经典书】计算理论导论，482页pdf
【经典书】计算理论导论，482页pdf
专知会员服务
78+阅读 · 2021年4月10日
【经典书】线性代数，436页pdf
专知会员服务
75+阅读 · 2021年3月16日
如何证明? 《Proofs: 长篇数学导论》硬核书，330页pdf
专知会员服务
115+阅读 · 2021年1月31日
【经典书】线性代数，Linear Algebra，525页pdf
【经典书】线性代数，Linear Algebra，525页pdf
专知会员服务
74+阅读 · 2021年1月29日
神经常微分方程教程，50页ppt，A brief tutorial on Neural ODEs
神经常微分方程教程，50页ppt，A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
神经网络序列数据建模，229页ppt，Modeling Sequential Data with Neural Nets
神经网络序列数据建模，229页ppt，Modeling Sequential Data with Neural Nets
专知会员服务
65+阅读 · 2020年7月25日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
92+阅读 · 2020年3月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
45+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
168+阅读 · 2019年10月11日
分布式并行架构Ray介绍
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
LibRec 精选：位置感知的长序列会话推荐
LibRec 精选：位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
在清华入党的那些事
在清华入党的那些事
清华大学研究生教育
14+阅读 · 2019年3月20日
逆强化学习-学习人先验的动机
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
可解释的CNN
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
【深度学习基础】4. Recurrent Neural Networks
【深度学习基础】4. Recurrent Neural Networks
微信AI
16+阅读 · 2017年7月19日
Unlinked monotone regression
Arxiv
0+阅读 · 2021年7月28日
Fusible HSTs and the randomized k-server conjecture
Arxiv
0+阅读 · 2021年7月28日
Recursive Estimation of a Failure Probability for a Lipschitz Function
Arxiv
0+阅读 · 2021年7月28日
Dynamic Programming and Linear Programming for Odds Problem
Arxiv
0+阅读 · 2021年7月28日
A new recursive spectral Tau method on system of generalized Abel-Volterra integral equations
Arxiv
0+阅读 · 2021年7月27日
Approximating Sumset Size
Arxiv
0+阅读 · 2021年7月26日
Finite-Bit Quantization For Distributed Algorithms With Linear Convergence
Finite-Bit Quantization For Distributed Algorithms With Linear Convergence
Arxiv
0+阅读 · 2021年7月23日
Distributed Graph Convolutional Networks
Arxiv
18+阅读 · 2020年7月13日
LPCNet: Improving Neural Speech Synthesis Through Linear Prediction
Arxiv
3+阅读 · 2018年10月28日
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
Arxiv
7+阅读 · 2018年6月1日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
相关VIP内容
【图神经网络导论】Intro to Graph Neural Networks，176页ppt
【图神经网络导论】Intro to Graph Neural Networks，176页ppt
专知会员服务
123+阅读 · 2021年6月4日
【经典书】计算理论导论，482页pdf
【经典书】计算理论导论，482页pdf
专知会员服务
78+阅读 · 2021年4月10日
【经典书】线性代数，436页pdf
专知会员服务
75+阅读 · 2021年3月16日
如何证明? 《Proofs: 长篇数学导论》硬核书，330页pdf
专知会员服务
115+阅读 · 2021年1月31日
【经典书】线性代数，Linear Algebra，525页pdf
【经典书】线性代数，Linear Algebra，525页pdf
专知会员服务
74+阅读 · 2021年1月29日
神经常微分方程教程，50页ppt，A brief tutorial on Neural ODEs
神经常微分方程教程，50页ppt，A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
神经网络序列数据建模，229页ppt，Modeling Sequential Data with Neural Nets
神经网络序列数据建模，229页ppt，Modeling Sequential Data with Neural Nets
专知会员服务
65+阅读 · 2020年7月25日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
92+阅读 · 2020年3月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
45+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
168+阅读 · 2019年10月11日
热门VIP内容
相关资讯
分布式并行架构Ray介绍
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
LibRec 精选：位置感知的长序列会话推荐
LibRec 精选：位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
在清华入党的那些事
在清华入党的那些事
清华大学研究生教育
14+阅读 · 2019年3月20日
逆强化学习-学习人先验的动机
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
可解释的CNN
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
【深度学习基础】4. Recurrent Neural Networks
【深度学习基础】4. Recurrent Neural Networks
微信AI
16+阅读 · 2017年7月19日
相关论文
Unlinked monotone regression
Arxiv
0+阅读 · 2021年7月28日
Fusible HSTs and the randomized k-server conjecture
Arxiv
0+阅读 · 2021年7月28日
Recursive Estimation of a Failure Probability for a Lipschitz Function
Arxiv
0+阅读 · 2021年7月28日
Dynamic Programming and Linear Programming for Odds Problem
Arxiv
0+阅读 · 2021年7月28日
A new recursive spectral Tau method on system of generalized Abel-Volterra integral equations
Arxiv
0+阅读 · 2021年7月27日
Approximating Sumset Size
Arxiv
0+阅读 · 2021年7月26日
Finite-Bit Quantization For Distributed Algorithms With Linear Convergence
Finite-Bit Quantization For Distributed Algorithms With Linear Convergence
Arxiv
0+阅读 · 2021年7月23日
Distributed Graph Convolutional Networks
Arxiv
18+阅读 · 2020年7月13日
LPCNet: Improving Neural Speech Synthesis Through Linear Prediction
Arxiv
3+阅读 · 2018年10月28日
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
Arxiv
7+阅读 · 2018年6月1日
Top
微信扫码咨询专知VIP会员
Top