Descriptive Complexity of Sensitivity of Cellular Automata

Favereau, Tom; Salo, Ville

数学 > 动力系统

arXiv:2504.05012 (math)

[提交于 2025年4月7日 (v1) ，最后修订 2025年5月5日 (此版本， v2)]

标题：细胞自动机敏感性的描述复杂性

标题： Descriptive Complexity of Sensitivity of Cellular Automata

Authors:Tom Favereau, Ville Salo

摘要：我们研究了确定细胞自动机是否对初始条件敏感的计算复杂性。我们证明该问题在一维中是$\Pi^0_2$完备的，在二维和更高维度中是$\Sigma^0_3$完备的。这解决了萨布莱克和泰斯耶提出的问题。

摘要： We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is $\Pi^0_2$-complete in dimension 1 and $\Sigma^0_3$-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.

评论：	16页，4个图，已被AUTOMATA 2025接受。已处理审稿人意见。
主题：	动力系统 (math.DS) ; 计算复杂性 (cs.CC); 逻辑 (math.LO)
MSC 类：	37B15 (Primary), 68Q80 (Secondary)
引用方式：	arXiv:2504.05012 [math.DS]
	(或者 arXiv:2504.05012v2 [math.DS] 对于此版本)
	https://doi.org/10.48550/arXiv.2504.05012

提交历史

来自： Tom Favereau [查看电子邮件]
[v1] 星期一， 2025 年 4 月 7 日 12:38:07 UTC (36 KB)
[v2] 星期一， 2025 年 5 月 5 日 11:58:31 UTC (29 KB)

数学 > 动力系统

标题：细胞自动机敏感性的描述复杂性

标题： Descriptive Complexity of Sensitivity of Cellular Automata

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

数学 > 动力系统

标题： 细胞自动机敏感性的描述复杂性 显示英文标题

标题： Descriptive Complexity of Sensitivity of Cellular Automata

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：细胞自动机敏感性的描述复杂性