Equational theories with no sublinear equational bound
by
Zoltan Szekely
Gallaudet University

The finite algebra membership problem of a given finite algebra F asks about the membership of any finite algebra in the variety generated by F. We may answer this decidable question via checking the equations true in F. The equational bound of the equational theory of F, as introduced by G. McNulty, tells us the length of equations we have to check in order to decide the membership of an input algebra of less than n elements. If F is finitely based then, obviously, we have a constant equational bound. We set up a sublinear lower bound on the equational bounds belonging to some small algebras built from a few well-known finite algebras, as the first nonfinitely based algebra discovered by Lyndon in 1954, or the algebra used to prove the nondecidability of Tarski's Finite Basis Problem by R. McKenzie in 1996.

Date received: June 27, 2002

Copyright © 2002 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 # caiv-30.