Structure and Algorithms, Between Logic and Algebra

项目负责人：Ralph mckenzie项目编号：0245622机构：Vanderbilt university结构和算法，在逻辑和代数之间肯齐将研究，一方面，涉及有限代数的性质的算法问题，这些性质是由它们产生的变量和拟变量决定的，另一方面，结构问题，涉及必须在局部有限变或拟变中为真的必要代数性质，作为该类具有通过逻辑或集合论方法定义的某些自然性质的结果。突出的算法问题：是否存在一种算法来确定在有限代数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.