Avoidability and Decidability in Formal Languages and Automata

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

• 批准号: 105829-2013
• 负责人: Shallit, Jeffrey
• 金额: $ 2.62万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569117
• 关键词: 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的n，该长度n是未订购的（不包含也没有后缀的非平凡前缀）。 我们与我的学生一起开发了理论工具来生成算法来解决这些问题，并且我们已经在软件中实施了这些问题。 结果，我们能够解决文献中的许多开放问题。 避免性源于挪威数学家Axel Thue的工作，他在1906年和1912年发表了两篇有影响力的论文。他表明，可以在三个字母的字母上构建一个无限的序列，其中包含两个相邻的块（of）任意尺寸），以及在两个字母字母上的无限序列，该序列不包含两个相邻的相同块，然后是第一个块的第一个字母。 现在在数十篇论文中研究了避免性，并在密码学上有一些应用。 我的工作涉及Thue问题的困难变化，例如在整数字母上避免使用相同大小和相同总和的连续三个块。 这将导致对序列中不可避免的规律的更深入了解。