Structure and Algorithms, Between Logic and Algebra

主要研究人员：Ralph McKenzie命题编号：0245622机构：范德比尔特大学摘要：结构与算法，逻辑与代数之间McKenzie一方面将研究算法问题，这些问题涉及由它们生成的簇和准簇确定的有限代数的性质，另一方面，结构问题涉及必要的代数属性，这些代数属性必须在局部有限簇或准簇中成立，因为该类具有通过逻辑或集合论方法定义的某些自然属性。悬而未决的算法问题：有没有一种算法来确定有限代数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.