Abstract:
In this paper we consider the well-known Turing machine model – nondeterministic real-time Turing machine. We prove the existence of nonregular complexity classes of languages that can be recognized by nondeterministic real-time Turing machines with sublogarithmic memory restrictions. These complexity classes form a strict hierarchy. We define a special language family and show its properties to prove that hierarchy.