A synchronizing word of a deterministic finite complete automaton is a word whose action maps every state to a single one. Finding a shortest or a short synchronizing word is a central computational problem in the theory of synchronizing automata and is applied in other areas such as model-based testing and the theory of codes. Because the problem of finding a shortest synchronizing word is computationally hard, among \emph{exact} algorithms only exponential ones are known. We redesign the previously fastest known exact algorithm based on the bidirectional breadth-first search and improve it with respect to time and space in a practical sense. We develop new algorithmic enhancements and adapt the algorithm to multithreaded and GPU computing. Our experiments show that the new algorithm is multiple times faster than the previously fastest one and its advantage quickly grows with the hardness of the problem instance. Given a modest time limit, we compute the lengths of the shortest synchronizing words for random binary automata up to 570 states, significantly beating the previous record. We refine the experimental estimation of the average reset threshold of these automata. Finally, we develop a general computational package devoted to the problem, where an efficient and practical implementation of our algorithm is included, together with several well-known heuristics.


翻译:确定性限定性完整自动图的同步单词是一个单词, 它的动作映射每个状态。 查找一个最短或最短同步的单词是同步自动数据理论中一个核心的计算问题, 并应用于其他领域, 如基于模型的测试和代码理论。 因为找到一个最短同步的单词的问题在计算上是困难的, 仅在指数性算法中是已知的 。 我们根据双向宽度第一搜索重新设计了以前最快已知的精确算法, 并在时间和空间方面从实际意义上加以改进。 我们开发了新的算法增强, 并将算法调整为多读和 GPU 计算。 我们的实验显示, 新的算法比以前最快的多倍, 其优势随着问题实例的难度而迅速增长。 由于时间有限, 我们计算了随机的双向自动数据最多达570 的最小同步单词的长度, 大大超过上一个记录。 我们改进了这些自动数据平均重置阈值的实验性估计值, 包括了我们几个实际化的算法, 最后, 我们开发了一个普通的算算法问题。

0
下载
关闭预览

相关内容

【2022新书】高效深度学习,Efficient Deep Learning Book
专知会员服务
115+阅读 · 2022年4月21日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
2+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
4+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年9月6日
Arxiv
13+阅读 · 2021年3月29日
Arxiv
31+阅读 · 2018年11月13日
VIP会员
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
2+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
4+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员