Algebraic methods in computational complexity and decidability

计算复杂性和可判定性的代数方法

• 批准号: 249684-2012
• 负责人: Delic, Dejan
• 金额: $ 0.87万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570686
• 关键词: Algebraic; methods; computational; complexity; decidability

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 one of the fundamental questions in the area of theoretical computer science about the complexity of computational queries occurring naturally in the area of artificial intelligence.

这是一份资助我正在进行的泛代数研究的提案，泛代数是纯数学的一个分支。 概括地说，我提出的研究的主要长期目标是：（1）发现数学知识的各个分支中的统一模式，如逻辑、代数和离散数学;（2）在适当的一般性水平上研究这些模式;（3）通过研究局部发生的现象来洞察全局结构;（4）通过拓宽各自领域的知识或找到多学科的应用，向一般数学界回报一些有价值的东西。 我的研究福尔斯主要落在方程逻辑及其算法方面的边界内。方程逻辑的主要研究对象是代数的非标准版本（方程理论）及其抽象模型。一般的问题是要确定在何种程度上的模型，这些非标准版本的代数可以描述。 更详细地说，我特别感兴趣的是使用组合几何性质的工具来研究代数和关系结构的局部结构;确定全局结构在多大程度上会受到这种局部行为的影响;以及这种性质是否可以在算法上得到识别;如果可以，这种算法是否在计算上易于处理。 该研究提案的动机，除其他问题外，在理论计算机科学领域的基本问题之一，在人工智能领域自然发生的计算查询的复杂性。