Finite decidability and generative complexity in equational classes
by
Ralph McKenzie
Vanderbilt University

The generative complexity of a class K of algebras (or structures) is the function G_K defined for positive integers n with G_K(n) equal to the number of non-isomorphic structures in K which can be generated by n or fewer elements. With P. Idziak and M. Valeriote, we proved that for a locally finite variety K, G_K is bounded by a polynomial function of its variable iff K decomposes into the varietal product of an affine variety over a ring of finite representation type and a finite sequence of combinatorial (i.e., strongly Abelian) varieties equivalent to matrix powers of varieties of H sets, with some constants, for various finite groups H.

A class K of structures is said to be finitely decidable if its class of finite members has decidable first order theory. Some arguments from the proof of the mentioned characterization of locally finite varieties with polynomially many models have been adapted by the author to prove several conjectured properties of the congruence relations that must hold in any finitely decidable locally finite variety. However, a structural characterization of all finitely generated finitely decidable varieties is not yet in hand. The talk will survey the mentioned results and provide some details.

Date received: July 2, 2004

Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caoc-10.