Zerotesting bounded one-way multicounter machines
Pavol Ďuriš, Juraj Hromkovic̆ · Czech digital mathematics library · 1987
ZEROTESTING BOUNDED ONE-WAY MULTICOUNTER MACHINES PAVOL ĎURIŠ, JURAJ HROMKOVIČ One-way multicounter machines with bounds on the number of reversals and zerotests in accepting computations are studied.The bounds are considered as functions of the length of input words.The first hieararchy results for nonconstant bounds on the number of zerotests are obtained.Further results relate the reversal complexity and zerotest complexity again in relation to nondeterminism, time, and the number of counters as additional complexity par ameters.