Hierarchy of reversal bounded one-way multicounter machines
Juraj Hromkovic̆ · Czech digital mathematics library · 1986
HIERARCHY OF REVERSAL BOUNDED ONE-WAY MULTICOUNTER MACHINES JURAJ HROMKOVIČWe consider one-way partially blind multicounter machines and one-way multicounter machi nes.We study the reversal bounded version of these machines, where for the input words of the length n the number of reversals is bounded by a function/(rc).It is established that time and nondeterminism, as the resources, cannot compensate for a substantial decrease of the number of reversals allowed.Several hierarchy results are consequences of this result.