Simulating one-reversal multicounter machines by partially blind multihead finite automata

AbstractThis work is concerned with simulating nondeterministic one-reversal multicounter automata (NCMs) by nondeterministic partially blind multihead finite automata (NFAs). We show that any one-reversal NCM with k counters can be simulated by a partially blind NFA with k blind heads. This provides a nearly complete categorization of the computational power of partially blind automata, showing that the power of a (k+1)-NFA lies between that of a k-NCM and a (k+1)-NCM