Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time

摘要

In this paper, we investigate the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each κ ≥ 1, there is a language accepted by a one-way Las Vegas κ-counter automaton operating in real time, but not accepted by any one-way deterministic κ-counter automaton operating in linear time, (2) there is a language accepted by a one-way self-verifying nondeterministic 2-counter automaton operating in real time, but not accepted by any oneway Las Vegas multi-counter automaton operating in polynomial time, (3) there is a language accepted by a one-way self-verifying nondeterministic 1-counter automaton operating in real time, but not accepted by any oneway deterministic multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a one-way nondeter-ministic 1-counter automaton operating in real time, but not accepted by any one-way self-verifying non-deterministic multi-counter automaton operating in polynomial time.