这篇论文研究一个有限或无限词与其卷曲数变换同时满足重复规避条件时的结构。针对大小为 2、3、4 的字母表,研究结合了形态构造、穷举有限搜索与自动化验证。
主要结果之一是:在三字母表上,一个词及其卷曲数变换若都要求 overlap-free,则长度最大只能达到 84;而在四字母表上可以构造出无限例子。因此,4 是允许两者同时无限保持 overlap-free 的最小字母表大小。
主要结果
论文解决了字母表大小为 2、3、4 时若干有限与无限的重复规避问题。无限构造使用 Walnut 进行验证,而有限极值结果则通过穷举搜索及独立复核得到。
我的贡献
我在这一项目中的工作包括独立复核主要的有限搜索结论、发现并修正若干数学定义与表述问题,以及重新组织论文的较大部分内容。具体来说,我独立验证了三字母情形长度 84 的极值障碍,修正了卷曲数变换的索引约定与 alpha-plus-free 的定义,并重新核对了四字母构造及其卷曲数变换。
计算验证
对于三字母极值情形,我独立重新运行了三组不同的穷举搜索。overlap-free / overlap-free 情形在长度 84 时有 6048 个候选,在长度 85 时为 0;9/4-free / overlap-free 情形对应为 10368 与 0;overlap-free / 7/3-free 情形则再次为 6048 与 0。我还整理并清理了该项目的补充验证文件。