Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complexity of an array of natural decision problems about presentations of sofic shifts, such as whether a given graph presents a shift of finite type, or an irreducible shift; whether one graph presents a subshift of another; and whether a given presentation is minimal, or has a synchronizing word. Leveraging connections to automata theory, we first observe that these problems are all decidable in polynomial time when the given presentation is irreducible (strongly connected), via algorithms both known and novel to this work. For the general (reducible) case, however, we show they are all PSPACE-complete. All but one of these problems (subshift) remain polynomial-time solvable when restricting to synchronizing deterministic presentations. We also study the size of synchronizing words and synchronizing deterministic presentations.


翻译: Sofic 转换是一组由边缘标签的定向图形(称为演示文稿)双无限制序列定义的象征性动态系统。我们研究了一系列自然决定问题的计算复杂性,这些自然决定问题涉及沉浮变化的演示,例如某个图形是显示一定类型的转变,还是不可减少的转变;一个图形是显示另一个的子转变;一个特定演示文稿是最小的,还是有同步的单词。利用自动磁盘连接理论,我们首先观察到,当给定的演示文稿不可复制(紧密连接)时,这些问题在多元时,通过已知的和对这项工作的新手算法都是可分解的。然而,对于一般(可减少的)案例,我们显示它们都是PSPACE的完整。在限制同步确定性演示时,除一个问题外,所有这些问题(次移)都仍然是多音时可溶解。我们还研究了同步的单词和同步确定性演示文稿的大小。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
专知会员服务
28+阅读 · 2021年8月2日
最新《高级算法》Advanced Algorithms,176页pdf
专知会员服务
90+阅读 · 2020年10月22日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年11月6日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年2月7日
Arxiv
1+阅读 · 2022年2月6日
Arxiv
0+阅读 · 2022年2月4日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
相关资讯
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年11月6日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员