Words avoiding Repetitions: Characterizations and Algorithms

避免重复的单词:特征和算法

基本信息

  • 批准号:
    418646-2012
  • 负责人:
  • 金额:
    $ 1.24万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2015
  • 资助国家:
    加拿大
  • 起止时间:
    2015-01-01 至 2016-12-31
  • 项目状态:
    已结题

项目摘要

My proposed research program is in the two areas of combinatorics on words and automata theory. Combinatorics on words is the study of the combinatorial properties of sequences over a finite set of symbols. It is an area at the intersection of discrete mathematics and formal language theory. I am especially interested in the avoidance of repetitions in words. My previous work in the area contributed to the resolution of Dejean's Conjecture, a long-standing open problem in the area. Many other interesting open problems concerning repetitions in words remain to be solved. Using the techniques developed for the proof of Dejean's Conjecture, I propose to investigate the structure of the words that achieve the repetition threshold described by the conjecture (now theorem). A characterization of such words is already known over the binary alphabet, but no such theory currently exists for larger alphabets. A characterization of this type for larger alphabets could lead to new results in transcendental number theory (as was the case for the binary alphabet). I also propose to study the infinite words that arise in the theory of numeration systems. A numeration system in the broadest sense is simply a system for representing integers by words. The classical integer base numeration systems are a special case of such numeration systems. A sequence of integers that can be computed by a finite automaton that processes its input in base-k is called a k-automatic sequence. Many combinatorial properties of k-automatic sequences, such as periodicity, or avoidance of repetitions, are algorithmically decidable. However, there is currently no general procedure to decide if a k-automatic sequence avoids Abelian repetitions (repetitions of the form xx' where x' is a permutation of x). With James Currie, we recently presented an algorithm that works on a large class of sequences. I would like to develop an algorithmic procedure that is completely general.
我建议的研究计划是在两个领域的组合词和自动机理论。词的组合学是研究有限符号集上序列的组合性质。它是离散数学和形式语言理论交叉的一个领域。 我特别感兴趣的是避免重复的话。我以前在该地区的工作有助于解决德让猜想,一个长期存在的开放问题在该地区。许多其他有趣的开放性问题,有关重复的话仍然有待解决。使用的技术开发的证明德让猜想,我建议调查的结构的话,实现重复阈值所描述的猜想(现在定理)。这种词的特征在二进制字母表中已经是已知的,但是对于较大的字母表,目前还不存在这样的理论。对较大字母表的这种类型的表征可能会导致超越数论的新结果(就像二进制字母表的情况一样)。 我还建议研究计数系统理论中出现的无限词。一个计数系统在最广泛的意义上是简单的一个系统表示整数的字。经典的整数基数制是这类数制的一个特例。一个整数序列可以由一个以k为底处理其输入的有限自动机计算出来,称为k-自动序列。k-自动序列的许多组合性质,如周期性或避免重复,是算法可判定的。然而,目前没有通用的程序来决定k-自动序列是否避免阿贝尔重复(形式为xx'的重复,其中x'是x的置换)。我们最近与James Currie一起提出了一种适用于一大类序列的算法。我想开发一个完全通用的算法程序。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Rampersad, Narad其他文献

Words avoiding repetitions in arithmetic progressions
  • DOI:
    10.1016/j.tcs.2007.10.039
  • 发表时间:
    2008-02-04
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Kao, Jui-Yi;Rampersad, Narad;Silva, Manuel
  • 通讯作者:
    Silva, Manuel
ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
On the asymptotic abelian complexity of morphic words
  • DOI:
    10.1016/j.aam.2014.08.005
  • 发表时间:
    2014-10-01
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Blanchet-Sadri, F.;Fox, Nathan;Rampersad, Narad
  • 通讯作者:
    Rampersad, Narad
A PROOF OF DEJEAN'S CONJECTURE
  • DOI:
    10.1090/s0025-5718-2010-02407-x
  • 发表时间:
    2011-04-01
  • 期刊:
  • 影响因子:
    2
  • 作者:
    Currie, James;Rampersad, Narad
  • 通讯作者:
    Rampersad, Narad
ON THE NUMBER OF ABELIAN BORDERED WORDS (WITH AN EXAMPLE OF AUTOMATIC THEOREM-PROVING)

Rampersad, Narad的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Rampersad, Narad', 18)}}的其他基金

Avoiding Generalized Repetitive Patterns in Words
避免单词中的普遍重复模式
  • 批准号:
    RGPIN-2019-04111
  • 财政年份:
    2022
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Avoiding Generalized Repetitive Patterns in Words
避免单词中的普遍重复模式
  • 批准号:
    RGPIN-2019-04111
  • 财政年份:
    2021
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Avoiding Generalized Repetitive Patterns in Words
避免单词中的普遍重复模式
  • 批准号:
    RGPIN-2019-04111
  • 财政年份:
    2020
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Avoiding Generalized Repetitive Patterns in Words
避免单词中的普遍重复模式
  • 批准号:
    RGPIN-2019-04111
  • 财政年份:
    2019
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Words avoiding Repetitions: Characterizations and Algorithms
避免重复的单词:特征和算法
  • 批准号:
    418646-2012
  • 财政年份:
    2018
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Words avoiding Repetitions: Characterizations and Algorithms
避免重复的单词:特征和算法
  • 批准号:
    418646-2012
  • 财政年份:
    2017
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Words avoiding Repetitions: Characterizations and Algorithms
避免重复的单词:特征和算法
  • 批准号:
    418646-2012
  • 财政年份:
    2014
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Words avoiding Repetitions: Characterizations and Algorithms
避免重复的单词:特征和算法
  • 批准号:
    418646-2012
  • 财政年份:
    2013
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Words avoiding Repetitions: Characterizations and Algorithms
避免重复的单词:特征和算法
  • 批准号:
    418646-2012
  • 财政年份:
    2012
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Discovery Grants Program - Individual
Combinatorics on words and formal languages
单词和形式语言的组合学
  • 批准号:
    343855-2007
  • 财政年份:
    2009
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Postdoctoral Fellowships

相似海外基金

XRN2-DDX23 Cooperation in Avoiding R-loop-induced Genomic Instability
XRN2-DDX23 合作避免 R 环引起的基因组不稳定
  • 批准号:
    10654331
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
Avoiding Cesarean-induced Obesity Through Hormone Rescue
通过激素拯救避免剖腹产引起的肥胖
  • 批准号:
    10628889
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
Preventing, avoiding and mitigating environmental impacts of fishing gears and associated marine litter
预防、避免和减轻渔具和相关海洋垃圾对环境的影响
  • 批准号:
    10066822
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
    EU-Funded
Calibration of Thermometers Avoiding the Use of Mercury
避免使用汞的温度计校准
  • 批准号:
    10061179
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Collaborative R&D
Development of an easily deployable user-counting system for avoiding human congestion
开发易于部署的用户计数系统,以避免人员拥堵
  • 批准号:
    23K11659
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
A Study on Breaking and Avoiding Relativization Barriers against Constructing One-Way Functions
打破和避免构建单向函数的相对化障碍的研究
  • 批准号:
    23K19957
  • 财政年份:
    2023
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Grant-in-Aid for Research Activity Start-up
Avoiding Diabetes After Pregnancy Together with Moms (ADAPT-M): Bridging care between the third and fourth trimester
与妈妈一起避免怀孕后糖尿病 (ADAPT-M):在妊娠晚期和妊娠晚期之间过渡护理
  • 批准号:
    480515
  • 财政年份:
    2022
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Operating Grants
Neurophysiological mechanisms of avoiding mental health risks during home teleworking and an efficient practical implementation framework
在家远程办公期间避免心理健康风险的神经生理机制及高效的实践实施框架
  • 批准号:
    22K04613
  • 财政年份:
    2022
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Collaborative Research: SaTC: CORE: Small: Improving Sanitization and Avoiding Denial of Service Through Correct and Safe Regexes
协作研究:SaTC:核心:小型:通过正确和安全的正则表达式改进清理并避免拒绝服务
  • 批准号:
    2135157
  • 财政年份:
    2022
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Standard Grant
Elucidation of the molecular mechanism of spermatogenesis avoiding meiosis in haploid males of Hymenoptera
膜翅目单倍体雄性精子发生避免减数分裂的分子机制的阐明
  • 批准号:
    22K05684
  • 财政年份:
    2022
  • 资助金额:
    $ 1.24万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了