Avoidability and Decidability in Formal Languages and Automata

我目前的研究涉及理论计算机科学的两个领域：(i)形式语言和自动机理论中问题的可决性和（ii）词语的可避免性。可判决性是理论计算机科学中一个古老的主题。这里我们有一些算法问题，想知道是否存在一种算法，能绝对正确地解决它。我工作的一个方面是解决涉及无限序列的可决性问题，特别是那些由自动机产生的问题。例如，子词复杂度（序列中长度为n的不同子块的数量）在文献中得到了广泛的研究。例如，我们可能想要描述存在长度为n的无边界子块（不包含同时也是后缀的非平凡前缀）的n。我和我的学生一起开发了理论工具来生成算法来解决这些问题，我们已经在软件中实现了它们。因此，我们已经能够解决文献中的一些开放问题。可回避性源于挪威数学家阿克塞尔·图伊（Axel Thue）的研究，他在1906年和1912年发表了两篇有影响力的论文。他证明了可以在三个字母的字母表上构造一个无限序列，其中不包含两个相邻的相同块（任意大小），也可以在两个字母的字母表上构造一个无限序列，其中不包含两个相邻的相同块，后面跟着第一个块的第一个字母。现在有几十篇论文对可避免性进行了研究，并在密码学中有一些应用。我的工作涉及Thue问题的复杂变体，例如在整数字母表中避免三个相同大小和相同总和的连续块的可能性。这将导致对序列中不可避免的规律有更深的理解。

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.