Algebra, logic, and complexity

代数、逻辑和复杂性

• 批准号: RGPIN-2020-05714
• 负责人: Valeriote, Matthew
• 金额: $ 1.75万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=717767
• 关键词: Algebra; logic; complexity

Algebraic structures arise in many different contexts, not only within mathematics, but in most of the sciences, and even in day to day life. For example, algebras known as groups are used to represent the symmetries of crystals and other physical systems, and Boolean algebras are used to codify rules of logic. Many other common systems, in particular those arising from questions in computer science can be viewed in an algebraic way. Thus research on algebraic structures can have an impact on several branches of the sciences and in particular on computer science. Several important properties of algebraic systems can be expressed via equations. For example, the fact that addition is commutative is expressed by the equation x + y = y + x. It has proved useful to organize and classify algebraic systems according to the equations that they satisfy. These equationally defined classes of algebras, called varieties, are objects that I study in my research. One of the long term objectives of my research is to investigate the connection between various types of complexities that can arise in varieties and the structure of the algebras that belong to them. A more recent direction that my research has taken relates to problems and questions from theoretical computer science. An important class of problems, known as constraint satisfaction problems (CSPs), has a natural expression in terms of finite algebras. CSPs are ubiquitous in many areas of artificial intelligence, computer science, and discrete mathematics, such as database theory, scheduling, and networking. A system of linear equations can be viewed as a special type of CSP. Another long term objective of my research is to understand the correlation between well behaved/manageable subclasses of CSPs and related problems and the structure of the corresponding algebraic systems that define them. In computer science, trees are a certain kind of ordered data type that can be used to store information that has a natural hierarchical structure. Depending on the complexity of the trees being considered, they can be processed by simple computing devices known as finite state tree automata. The collection of trees that a given finite state tree automaton can process is called a regular tree language. A big open problem in automata theory is to find an effective characterization of regular tree languages that can be defined using a first order sentence. A long term objective of my research is to solve this problem and to more generally investigate regular tree languages from the perspective of definability.

代数结构出现在许多不同的背景下，不仅在数学中，而且在大多数科学中，甚至在日常生活中。例如，被称为群的代数被用来表示晶体和其他物理系统的对称性，布尔代数被用来编纂逻辑规则。许多其他常见的系统，特别是那些在计算机科学中产生的问题，可以被视为在代数的方式。因此，对代数结构的研究可以对科学的几个分支产生影响，特别是对计算机科学。 代数系统的几个重要性质可以通过方程来表达。例如，加法是可交换的这一事实可以用方程x + y = y + x来表示。它已被证明是有用的组织和分类代数系统根据方程，他们满足。这些用等式定义的代数类，称为簇，是我研究的对象。我的研究的长期目标之一是研究各种类型的复杂性之间的联系，这些复杂性可能出现在各种各样的代数和属于它们的代数结构之间。 我最近的研究方向涉及理论计算机科学的问题。一类重要的问题，被称为约束满足问题（CSP），有一个自然的表达有限代数。CSP在人工智能、计算机科学和离散数学的许多领域中无处不在，例如数据库理论、调度和网络。线性方程组可以被看作是CSP的一种特殊类型。我的研究的另一个长期目标是了解良好的行为/可管理的CSP和相关问题的子类和相应的代数系统，定义它们的结构之间的相关性。 在计算机科学中，树是一种有序的数据类型，可用于存储具有自然层次结构的信息。 根据所考虑的树的复杂性，它们可以被称为有限状态树自动机的简单计算设备处理。 给定的有限状态树自动机可以处理的树的集合被称为正则树语言。自动机理论中的一个大的开放问题是找到一个可以使用一阶句子定义的正则树语言的有效特征。我研究的一个长期目标是解决这个问题，并从可定义性的角度更广泛地研究正则树语言。