Complexity and decidability of algebraic and relational structures

这项建议是为了资助我正在进行的普适代数研究，普适代数是纯数学的一个分支。从广义上讲，我建议的研究的主要长期目标是(1)发现不同数学知识分支中的统一模式，如逻辑、代数和离散数学；(2)在适当的概括性水平上研究这些模式；(3)通过研究局部发生的现象来洞察全球结构；以及(4)通过扩大各自领域的知识，或通过寻找多学科应用，将一些有价值的东西返还给普通数学界。我的研究大多属于等式逻辑及其算法方面的范畴。方程式逻辑的主要研究对象是非标准版本的代数(方程式理论)及其抽象模型。一般的问题是确定这些非标准版本的代数的模型可以在多大程度上被描述。更详细地说，我特别感兴趣的是使用组合几何性质的工具来研究代数和关系结构的局部结构；确定这种局部行为将在多大程度上影响全局结构；以及这些性质是否可以通过算法识别；如果是这样的话，这样的算法是否在计算上容易处理。这一研究建议的动机之一是泛代数领域中一个长期存在的公开问题，即刻画所有有限可判定的局部有限簇。我的目标是通过使用驯服同余理论和模型理论的方法来解决这个问题，为我的研究领域做出重大贡献。

This is a proposal to fund my ongoing research in universal algebra, which is a branch of pure mathematics. Broadly speaking, the main long-term goals of my proposed research are (1) to discover unifying patterns in various branches of mathematical knowledge, such as logic,algebra, and discrete mathematics; (2) to study these patterns at an appropriate level of generality; (3) to provide insight into global structure by studying phenomena that occur locally; and (4) to return something of the value to the general mathematical community, by either broadening the knowledge in the respective areas, or by finding multi-disciplinary applications. My research falls mostly within the boundaries of equational logic and its algorithmic aspects. The main object of study of equational logic are nonstandard versions of algebra (equational theories) and their abstract models. The general problem is to determine to what extent the models of these nonstandard versions of algebra can be described. In more detail, I am particularly interested in using the tools of combinatorial-geometric nature to study the local structure of algebras and relational structures; to determine to what extent the global structure will be influenced by this local behaviour; and whether such properties can be recognized algorithmically; and, if so, whether such an algorithm is computationally tractable. The research proposal is motivated, among other questions, by a long-standing open problem in the field of universal algebra, which is to characterize all finitely decidable locally finite varieties.   I aim to make a major contribution in my field of research by solving this problem using the methods of tame congruence theory and model theory.