Avoidability and Decidability in Formal Languages and Automata

形式语言和自动机中的可避免性和可判定性

基本信息

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

项目摘要

My current research involves two areas from theoretical computer science: (i) decidability of problems in formal languages and automata theory and (ii) avoidability in words.Decidability is an old theme in theoretical computer science. Here we have some algorithmic problem and want to know if there exists an algorithm that will infallibly solve it. One aspect of my work addresses decidability questions involving infinite sequences, particularly those generated by automata. For example, subword complexity (the number of distinct sub-blocks of length n in the sequence) has been widely studied in the literature. We might want to characterize, for example, the n for which there exists a sub-block of length n that is unbordered (contains no nontrivial prefix that is also a suffix). Together with my students, we have developed theoretical tools to generate algorithms to solve these problems, and we have implemented them in software. As a result, we have been able to solve a number of open problems in the literature.Avoidability has its roots in the work of Axel Thue, a Norwegian mathematician who published two influential papers in 1906 and 1912. He showed that it is possible to construct an infinite sequence over a three-letter alphabet that contains no two adjacent identical blocks (of arbitrary size), and an infinite sequence over a two-letter alphabet that contains no two adjacent identical blocks followed by the first letter of the first block. Avoidability is now studied in dozens of papers and has some applications to cryptography. My work concerns difficult variations of Thue's problem, such as the possibility of avoiding, over an integer alphabet, three consecutive blocks of the same size and same sum. This will lead to deeper understanding of the inevitable regularities in sequences.
我目前的研究涉及理论计算机科学的两个领域:(I)形式语言和自动机理论中的问题的可判断性和(Ii)词的可避性。这里我们遇到了一些算法问题,我们想知道是否存在一个算法可以无懈可击地解决它。我的工作的一个方面是解决涉及无限序列的可判断性问题,特别是那些由自动机生成的序列。例如,子字复杂度(序列中长度为n的不同子块的数量)在文献中已被广泛研究。例如,我们可能想要刻画存在长度为n的无边界子块(不包含也是后缀的非平凡前缀)的n。与我的学生们一起,我们开发了理论工具来生成解决这些问题的算法,并在软件中实现了它们。因此,我们已经能够解决文献中的一些悬而未决的问题。规避源于挪威数学家阿克塞尔·图的工作,他在1906年和1912年发表了两篇有影响力的论文。他证明了在不包含两个相邻的相同块(任意大小)的三个字母表上构造一个无限序列是可能的,在不包含两个相邻的相同块后跟第一个块的第一个字母的两个字母表上构造一个无限序列是可能的。可避免性现在已经在几十篇论文中进行了研究,并在密码学中有一些应用。我的工作涉及图厄问题的困难变体,例如在整数字母表上避免相同大小和相同和的三个连续块的可能性。这将导致对序列中不可避免的规律的更深层次的理解。

项目成果

期刊论文数量(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 }}

Shallit, Jeffrey其他文献

Avoiding squares and overlaps over the natural numbers
  • DOI:
    10.1016/j.disc.2009.06.004
  • 发表时间:
    2009-11-06
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Guay-Paquet, Mathieu;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Avoiding 3/2-powers over the natural numbers
  • DOI:
    10.1016/j.disc.2011.12.019
  • 发表时间:
    2012-03-28
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Rowland, Eric;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
A pattern sequence approach to Stern's sequence
  • DOI:
    10.1016/j.disc.2011.07.029
  • 发表时间:
    2011-11-28
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Coons, Michael;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Efficient enumeration of words in regular languages
  • DOI:
    10.1016/j.tcs.2009.03.018
  • 发表时间:
    2009-09-01
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Ackerman, Margareta;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Decidability of Sturmian Words
Sturmian 单词的可判定性

Shallit, Jeffrey的其他文献

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

{{ truncateString('Shallit, Jeffrey', 18)}}的其他基金

Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2022
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2021
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2020
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2019
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2018
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2016
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2015
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2014
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2013
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Descriptional complexity, combinatorics on words, formal languages and number theory
描述复杂性、单词组合学、形式语言和数论
  • 批准号:
    105829-2008
  • 财政年份:
    2012
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

Heights, Dynamics, and Decidability
高度、动态和可判定性
  • 批准号:
    RGPIN-2022-02951
  • 财政年份:
    2022
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Algebraicity, Transcendence, and Decidability in Arithmetic and Geometry through Model Theory
通过模型理论研究算术和几何中的代数性、超越性和可判定性
  • 批准号:
    2201045
  • 财政年份:
    2022
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Continuing Grant
Geometry and decidability in infinite groups
无限群中的几何和可判定性
  • 批准号:
    2770835
  • 财政年份:
    2022
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Studentship
Analysis on the decidability of the almost-universality problem for higher-order languages
高阶语言几乎普遍性问题的可判定性分析
  • 批准号:
    19K14582
  • 财政年份:
    2019
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Formalization of the decidability of the reachability problem for vector addition systems
向量加法系统可达性问题可判定性的形式化
  • 批准号:
    18K11154
  • 财政年份:
    2018
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Definability and decidability in global and local fields
全局和局部领域的可定义性和可判定性
  • 批准号:
    404427454
  • 财政年份:
    2018
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Research Grants
Algebraic methods in computational complexity and decidability
计算复杂性和可判定性的代数方法
  • 批准号:
    249684-2012
  • 财政年份:
    2017
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2016
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2015
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Algebraic methods in computational complexity and decidability
计算复杂性和可判定性的代数方法
  • 批准号:
    249684-2012
  • 财政年份:
    2015
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了