A note on real-time one-way alternating multicounter machines (Q809610): Difference between revisions

The computational power of one-way alternating multicounter machines is investigated. The main results of the paper are: 1) one-way real-time alternating \((k+1)\)-counter are more powerful than one-way real-time k-counter ones for each positive integer k, and 2) one-way linear-time alternating k-counter machines are more powerful than one-way real-time k-counter ones for \(k\geq 2.\) Besides these results some closure properties of the above considered machines are investigated. The paper includes an interesting version of the lower bound proof technique based on the crossing sequence argument.