Two-way deterministic multi-weak-counter machines

In this paper, we consider two-way deterministic machines which have counters, each capable of storing any nonnegative integer, but not having the ability to detect empty counter, and which accept by final state. We call these machines two-way deterministic multi-weak-counter machines. Let 2NWC^(k) and 2DWC^(k) denote the classes of languages recognized by two-way nondeterministic and deterministic k-weak-counter machines, respectively. In particular, for k = 1, we denote the corresponding classes by 2NWC and 2DWC. The following results are shown: (1) 2DWC^(k) = 2DWCfork ?1. (2) A bounded language in 2DWC is a bounded semilinear language. (3) 2NWC ≠ 2DWC.