Computational and combinatorial approaches to periodicities in strings

字符串周期性的计算和组合方法

• 批准号: 25112-2012
• 负责人: Franek, Frantisek
• 金额: $ 1.02万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=592991
• 关键词: Computational; combinatorial; approaches; periodicities; strings

The periodicities of strings are of interest for many applications such as data compression, text retrieval, and DNA or protein sequencing. The fundamental periodicities in a string include distinct squares and runs. My proposal has two objectives, the main dealing with a deeper understanding of the fundamental periodicities and their computations, and the secondary with improving upper bounds to graphs disproving an Erdös' conjecture.

字符串的周期性对于数据压缩、文本检索以及 DNA 或蛋白质测序等许多应用都很重要。字符串中的基本周期性包括不同的平方和游程。我的建议有两个目标，主要是对基本周期性及其计算有更深入的理解，其次是改进图的上限，反驳埃尔多斯的猜想。