Structure and Algorithms, Between Logic and Algebra

首席研究员：拉尔夫·麦肯齐提案编号：0245622机构：范德比尔特大学摘要：逻辑与代数之间的结构和算法麦肯齐将一方面研究涉及有限代数性质的算法问题，这些性质由它们生成的簇和准簇决定，另一方面涉及结构问题，涉及必要的代数性质，这些性质在整个局部有限簇中必须成立。或准多样性，因为该类别拥有通过逻辑或集合论手段定义的某些自然属性。 突出的算法问题：是否有一种算法可以确定有限代数 F 中有效的拟方程是否是有限基的？ 有没有一种算法可以判断F生成的准品种是否具有自然对偶性？ 具有有限方程基的有限代数类是否可递归枚举？ 生成剩余大变量的有限代数类是否可递归枚举？ 重要的结构问题包括：什么样的代数性质集合对于有限生成的簇是有限可判定的或具有很少的模型是必要且充分的？ 今天，普通代数这一分支的纯粹理论研究并不是由满足任何紧迫的实际需求的可能性所驱动，而是由智力挑战的绝对难度和伴随成功而来的巨大满足感所驱动。 然而，像所有代数一样，这项工作催生了源源不断的算法，其中许多虽然可行，但很难在计算机上有效实现，从而对硬件、软件和编程技能的最新水平提出了严格的考验。 当前的方程逻辑定理证明程序就是这种现象的一个很好的例子。 理论计算机科学界似乎越来越认识到，一般代数是他们最需要熟练掌握的数学语言。 首席研究员认为，一方面，对识别有限代数基本性质的算法是否存在，另一方面，对代数中所体现的结构复杂性水平（本项目的全部内容）之间的相互作用进行研究，不仅有可能扩大我们对有限代数系统中结构可能性的理解（它已经做到了），而且有朝一日可以产生用于安全信息传输的高级代码和密码。

Principal Investigator: Ralph McKenzieProposal Number: 0245622Institution: Vanderbilt UniversityAbstract: Structure and algorithms, between logic and algebraMcKenzie will investigate, on the one hand, algorithmic questions which involve properties of finite algebras determined by the varieties and quasi-varieties they generate, and, on the other hand, structural questions which involve the necessary algebraic properties that must be true throughout a locally finite variety or quasi-variety as a consequence of that class possessing some natural property defined through logical or set-theoretic means. The outstanding algorithmic questions: Is there an algorithm to determine whether the quasi-equations valid in a finite algebra F are finitely based? Is there an algorithm to determine if the quasi-variety generated by F possesses a natural duality? Is the class of finite algebras possessing a finite equational basis recursively enumerable? Is the class of finite algebras generating a residually large variety recursively enumerable? Among the important structural questions: What collection of algebraic properties is necessary and sufficient for a finitely generated variety to be finitely decidable, or to have few models? Purely theoretical research in this branch of general algebra is driven today not by the likelihood of supplying any pressing practical needs, but rather by the sheer difficulty of the intellectual challenge and the tremendous sense of satisfaction that accompanies success. However, this work, like all of algebra, spawns a constant stream of algorithms, many of which, though feasible, are extremely difficult to implement efficiently on a computer, providing a severe test of the state-of-the-art in hardware and software and programming skills. The current theorem-proving programs for equational logic are a good example of this phenomenon. There appears to be a growing realization in the theoretical computer science community that general algebra is the mathematical language in which they most need to be fluent. The principal investigator believes that research into the interplay between, on the one hand, the existence or nonexistence of algorithms to recognize fundamental properties of finite algebras, and on the other hand, the levels of structural complexity manifested in the algebras---what this project is all about---has the potential not only to expand our understanding of the structural possibilities in finite algebraic systems (which it has already done), but to produce, some day, superior codes and ciphers for secure information transfer.