Avoidability and Decidability in Formal Languages and Automata

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

• 批准号: 105829-2013
• 负责人: Shallit, Jeffrey
• 金额: $ 2.62万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634813
• 关键词: Avoidability; Decidability; Formal; Languages; Automata

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年发表了两篇有影响力的论文。他证明了在不包含两个相邻的相同块(任意大小)的三个字母表上构造一个无限序列是可能的，在不包含两个相邻的相同块后跟第一个块的第一个字母的两个字母表上构造一个无限序列是可能的。可避免性现在已经在几十篇论文中进行了研究，并在密码学中有一些应用。我的工作涉及图厄问题的困难变体，例如在整数字母表上避免相同大小和相同和的三个连续块的可能性。这将导致对序列中不可避免的规律的更深层次的理解。