Remarks on the complexity of nondeterministic counter languages

AbstractFor classes of languages accepted in polynomial time by multicounter machines, various trade-offs in computing power obtain among the number of counters, the amount of time, and the amount of space required in all cases, deterministic and nondeterministic, on-line and off-line. Hierarchies can be obtained in all cases by varying the number of counters or the amount of time allowed. In the on-line case, nondeterministic counter machines are always more powerful than deterministic counter machines for the same number of counters and the same polynomial time bound. Relationships with open problems are explored