Algorithmic Combinatorics on Sequences

对词的组合和算法特性的研究是理论计算机科学的中心课题，在数据压缩、密码学、语言理论以及算法学习理论、数据库理论、生物信息学或分子生物学中都有许多应用。最初受到词的组合学和算法的两个核心问题，即模式匹配和求解词方程的启发，我们提出了一系列新的组合和算法问题的研究。在我们处理的主要议题中，我们提到：有效匹配各种类型的二阶模式（即，除了常量符号外，还包含词变量和函数变量的模式），识别可有效确定其可满足性的相关类词方程，了解解决其他类词方程的难度来源，以及分析近似模式匹配问题和与将单词分解为具有特定组合属性的因子（例如，正方形，回文）的可能性相关的问题。

The study of the combinatorial and algorithmic properties of words is a central topic in theoretical computer science, finding many applications in data compression, cryptography, language theory, as well as in algorithmic learning theory, data-base theory, bioinformatics or molecular biology. Initially motivated by two of the central problems in combinatorics and algorithmics on words, namely pattern matching and solving word equations, we propose the investigation of a series of novel combinatorial and algorithmic questions. Among the main topics we approach, we mention: efficiently matching various types of second-order patterns (i.e., patterns that contain, besides constant symbols, both word- and function- variables), identifying relevant classes of word equations whose satisfiability can be efficiently decided, understanding where the hardness of solving other classes of word equations originates, as well as analysing approximate pattern matching problems and questions related to the possibility of factoring a word in factors with specific combinatorial properties (e.g., squares, palindromes).