Grandjean, Olive and Pudlák established the variable hierarchy
for spectra of sentences using relation and function
symbols [1]}, [2]}, [3]}, [4]}, [5]}.
Let \(\textsc {NRAM}[N^k]\)  denote the class of sets of positive integers
accepted by a non-deterministic RAM in time \(O(N^k)\) ,
and \(N\)  is the input integer.
In his series of papers, Grandjean showed that
the class \(\textsc {NRAM}[N^k]\)  is precisely the class of the spectra
of first-order sentences written in prenex normal form
using only universal quantifiers and \(k\)  variables
with vocabulary consisting of relation and function symbols of
arity \(k\)  [1]}, [2]}, [3]}.
By Skolemisation, this result leads to the fact that for every integer \(k \geqslant 1\) ,
the class of spectra of first-order sentences using relation and
function symbols and \(k\)  variables
is precisely \(\textsc {NRAM}[N^k]\) .
See also [4]}.
