GEORGE F. McNULTY
Department of Mathematics, University of South Carolina, Columbia SC 29208, USA
ZOLTÁN SZÉKELY
Division of Mathematical Sciences, College of Natural and Applied Sciences, University of Guam, UOG Station, Mangilao, GU 96923, USA
ROSS WILLARD
Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

In Celebration of the Accomplishments of Béla Csákány

Received 28 July 2006
Revised 5 August 2008

We associate to each variety of algebras of finite signature a function on the positive integers called the equational complexity of the variety. This function is a measure of how much of the equational theory of a variety must be tested to determine whether a finite algebra belongs to the variety. We provide general methods for giving upper and lower bounds on the growth of equational complexity functions and provide examples using algebras created from graphs and from finite automata. We also show that finite algebras which are inherently nonfinitely based via the shift automorphism method cannot be used to settle an old problem of Eilenberg and Schützenberger.

Equational complexity; variety of algebras; inherently nonfinitely based; shift automorphism method; graph algebra; automatic algebra
AMSC numbers: 08B05, 03C05, 68Q17