Refining Nondeterminism Below Linear Time
Martin Kutrib, Justus Liebig University Giessen · University writing server of the Justus Liebig University Giessen (Justus-Liebig-Universität Gießen) · 2001
Multitape Turing machines with a restricted number of nondeterministic steps are investigated. Fischer and Kintala showed an infinite nondeterministic hierarchy of properly included real-time languages between the deterministic languages and the log-bounded nondeterministic languages. This result is extended to time complexities in the range between real time and linear time, and is generalized to arbitrary dimensions. For fixed amounts of nondeterminism infinite 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.