Structure and Algorithms, Between Logic and Algebra

主要研究者：Ralph McKenzie提案编号：0245622机构：范德比尔特大学摘要：结构和算法之间的逻辑和algebraMcKenzie将调查，一方面，算法问题，其中涉及有限代数的性质所确定的品种和准品种，他们产生的，而且，另一方面，结构问题，其中涉及必要的代数性质，必须是真实的整个局部有限品种或准，由于该类拥有通过逻辑或集合论方法定义的某些自然属性而产生的变种。 突出的算法问题：是否有一个算法来确定是否在有限代数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.