In a one-way multicomputer machine, each pushdown store has a single symbol in its tape alphabet, making each store a counter. A one-way alternating multicounter machine M divides the states into disjoint sets of universal and existential states. In a computation tree, each universal state leads to a series of successor states, and each existential state leads to a single successor state. In an accepting computation for M, each leaf must correspond to an accepting state. The class of languages recognizable by such a machine with k counters operating in real time is 1ACM ( k , real ); the class recognizable in linear time is 1ACM ( k , linear ).

In this paper, the authors extend some previous results about counter machines to alternating multicounter machines. First, they demonstrate the power of alternation by exhibiting a language that can be recognized in real time by an alternating machine with a single counter; this language cannot be accepted in time T ( n ) = n ^r for any r by a nondeterministic multicounter machine. The main  theorem  of the paper shows that for each k, 1ACM ( k , real ) is a proper subset of 1ACM ( k + 1 , real ). To demonstrate the power of linear time, the authors show that a language exists that can be recognized in linear time by a deterministic counter machine with just two counters, but this language is not in 1ACM ( k , eal ) for any k. In fact, for each k > 1 , 1ACM ( k , real ) is a proper subset of 1ACM ( k , linear ). (The authors conjecture that the classes are equal for k = 1 .) Finally, the authors investigate closure results for the various classes.

The paper is well written, and the authors are careful to distinguish among the various classes of machines and languages. Their explanations and proofs are clear, and they provide a number of open problems.