Structure and Algorithms, Between Logic and Algebra

Vanderbilt University, Nashville TN

Investigators

Abstract

Principal Investigator: Ralph McKenzie Proposal Number: 0245622 Institution: Vanderbilt University Abstract: Structure and algorithms, between logic and algebra McKenzie 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.