Combinatorics of Word Morphisms

组合模式匹配是理论计算机科学的一个领域，研究有限和无限符号序列（也称为单词或字符串）的组合和算法特性。该领域位于代数、组合学、复杂性理论和算法理论的交叉点，在数据压缩、密码学、语言理论以及生物信息学或数据挖掘中有多种应用。该领域的核心主题之一是对词态的组合和算法特性的理解。我们建议从算法和数学两个角度来研究词态。从算法的角度出发，重点研究了词方程的可满足性问题。给定两个包含常量和变量的单词，我们感兴趣的是是否存在一种方法来替换变量（即，将变量映射到常量字符串的态射），从而使两个单词相等。这个问题概括了许多研究得很好的模式匹配问题，其中一些非常实用，并且有有效的解决方案，例如，检查较短的文本是否出现在较长的文本中。然而，确定词方程可满足性问题的确切时间复杂度尚不清楚。众所周知，词方程可以在线性非确定性空间中求解，并且该问题是$\npclass$-hard。这表明，一般来说，构造满足一组预定义条件的词态是一个计算困难的问题。我们对这一主题的研究提出了对一般词方程的可满足性问题的复杂性的深入研究，以及对由各种数值和结构参数定义的各种受限但有意义的方程的复杂性的研究，其中甚至可以获得有效的算法。从数学的角度，我们打算丰富词态的组合和代数性质的研究。在这个重点中，我们对相等集（在两个给定的态射下相等的词集）的结构和组合性质的研究感兴趣。这个主题与可计算性和复杂性领域有着深刻的联系。例如，著名的后对应问题可以表示为两个给定态射的相等集的空性问题。此外，词方程系统的代数维数性质也是我们感兴趣的。例如，在固定数量的变量上找到独立方程组的最大大小是一个长期存在的开放问题；解决这类问题需要对表示独立方程解的态射的组合学有很好的理解。

Combinatorial pattern matching is the area of theoretical computer science that is concerned with the study of combinatorial and algorithmic properties of finite and infinite sequences of symbols (also called words or strings). This field lies at the crossroads of algebra, combinatorics, complexity theory, and algorithms theory, and has multiple applications in data compression, cryptography, language theory, but also bioinformatics or data mining. One of the core topics within this area is the understanding of combinatorial and algorithmic properties of word-morphisms. We propose the study of word-morphisms from two points of view: algorithmic and mathematical. From an algorithmic point of view, we focus on the satisfiability problem for word equations. Given two words containing constants and variables, we are interested in whether there exists a way to replace the variables (i.e., a morphism mapping the variables to strings of constants) that makes the two words equal. This problem generalises a multitude of well studied pattern matching problems, some of them very practical and with efficient solutions, e.g., checking whether a shorter text appears in a longer one. However, the exact time complexity of deciding the satisfiability problem for word equations is not yet known. It is known that word equations can be solved in linear non-deterministic space, and that the problem is $\npclass$-hard. This suggests that, in general, constructing word-morphisms that fulfil a set of predefined conditions is a computationally hard problem. Our research on this topic proposes a thorough investigation of the complexity of the satisfiability problem for general word equations, but also for various classes of restricted, yet meaningful, equations, defined by various numerical and structural parameters, where even efficient algorithms could be obtained. From a mathematical point of view, we intend to enrich the study of combinatorial and algebraic properties of word-morphisms. Within this focus point, we are interested in the investigation of structural and combinatorial properties of equality sets (sets of words which are equal under two given morphisms). This topic has deep connections to the areas of computability and complexity. For instance, the the famous Post Correspondence Problem can be expressed as the emptiness problem for the equality set of two given morphisms. Moreover, algebraic dimension properties of systems of word equations are of interest to us. For instance, it is a long standing open problem to find the maximum size of independent systems of equations over a fixed number of variables; it is expected that solving such problems requires a good understanding of the combinatorics of morphisms that represent the solutions to independent equations.