The authors study some decision questions concerning two-way counter machines and obtain the strongest decidable results to date concerning these machines. In particular, it is shown that the emptiness, containment, and equivalence (ECE for short) problems are decidable for two-way counter machines whose counter is reversal-bounded (i.e., the counter alternates between increasing and decreasing modes at most a fixed number of times). This result is used to give a simpler proof of a recent result which shows that the ECE problems for two-way reversal-bounded pushdown automata accepting bounded languages (i.e., subsets of $w_{1}^{*} \dotsc w_{k}^{*}$ for some nonnull words $w_{1}, \dotsc , w_{k}$) are decidable. Other applications concern decision questions about simple programs. Finally, it is shown that nondeterministic two-way reversal-bounded multicounter machines are effectively equivalent to finite automata on unary languages, and hence their ECE problems are decidable also.

The authors give an efficient parallel algorithm for the string edit problem. The model of computation is a one-way linear array of identical finite-state machines (nodes). The data movement in the array is one-way, from left to right. For inputs of length n, the array uses n nodes. The algorithm can produce the actual minimum-cost edit sequence in linear time. The previous parallel algorithm for this problem runs in O(n) time on a one-way two-dimensional array of finite-state machines using n/sup 2/ nodes. The best serial (RAM) algorithm for the problem takes O(n/sup 2//log n) time and space. Applications to other problems such as the longest common subsequence and approximate pattern matching are discussed.>