提出词链生成器，揭示前缀正则词的结构特性
Word Chain Generators for Prefix Normal Words
- 用词链和生成器建立同长词间的关联关系
- 发现非前缀正则词的关键因子特征
- 为枚举与测试提供新思路，适合形式语言研究者
2011年，Fici和Lipták引入了前缀正则词。二进制词是前缀正则的，当且仅当其任意子串中1的个数不超过同长度前缀中的1的个数。关于该主题的开放问题包括前缀正则词的计数及高效检测方法。本文揭示了前缀正则词的一系列特性，包括导致某词不满足前缀正则性的因子性质。通过词链与生成器，提出了同长度词间的新关联方式。
原文摘要 · Abstract (English)
In 2011, Fici and Lipták introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the prefix of the same length. Among the open problems regarding this topic are the enumeration of prefix normal words and efficient testing methods. We show a range of characteristics of prefix normal words. These include properties of factors that are responsible for a word not being prefix normal. With word chains and generators, we introduce new ways of relating words of the same length to each other.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。