Recently, infinite time hierarchies of separated complexity classes in the range between real time and linear time have been shown. This result is generalized to arbitrary dimensions. Furthermore, for fixed time complexities of the form id + r, where r E o(id) is a sublinear function, proper dimension hierarchies are presented. The hierarchy results are established by counting arguments. For an equivalence relation and a family of witness languages the number of induced equivalence classes is compared to the number of equivalence classes distinguishable by the model in question. By contradiction the properness of the inclusions is proved.
['Martin Kutrib']
Dimension- and Time-Hierarchies for Small Time Bounds