THE DATA TYPE VARIETY OF STACK ALGEBRAS

We define and study the class of all stack algebras as the class of al l minimal algebras in a variety defined by an infinite recursively enu merable set of equations. Among a number of results, we show that the initial model of the variety is computable, that its equational theory is decidable, but that its equational deduction problem is undecidabl e. We show that it cannot be finitely axiomatised by equations, but it can be finitely axiomatised by equations with a hidden sort and funct ions. This class of all stack algebras, together with its specificatio ns, can be used to survey the many models in the literature on stacks in a systematic way, and hence give the study of the stack some mathem atical coherence.