We will only define \(\)  and \(\)  informally here, and refer to [1]} for a formal definition.
A one-way nondeterministic counter machine can be defined equivalently to a one-way nondeterministic pushdown automaton [2]} with only a bottom-of-pushdown marker plus one other symbol. Hence, the machine can add to the counter (by pushing), subtract from the counter (by popping), and can detect emptiness and non-emptiness of the pushdown. A \(k\) -counter machine has \(k\)  independent counters. A \(k\) -counter machine \(M\)  is \(l\) -reversal-bounded, if \(M\)  makes at most \(l\)  changes between non-decreasing and non-increasing of each counter in every accepting computation. Let \(\)  be the class of one-way nondeterministic \(l\) -reversal-bounded \(k\) -counter machines, for some \(k,l\)  (\(\)  for deterministic machines). Let \(\)  be the class of machines with one unrestricted pushdown plus some number of reversal-bounded counters. By a slight abuse of notation, we also use these names for the family of languages they accept.
