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