One-way weak-stack-counter automata

摘要

Stack-counter automata are defined as one-way stack automata with a storage alphabet of just one symbol and the ability to recognize the left (bottom) and right (top) ends of the stack. Weak-stack-counter automata considered in this paper are stack-counter automata which do not have the ability to recognize the left end of the stack. We show that stack-counter automata are more powerful than weak-stack-counter automata. This answers the open question given by S. Ginsburg and G. F. Rose (J. Comput. System Sci. 8 (1974), 243–269). We also show that nondeterministic weak-stack-counter automata that accept by simultaneous terminal (final) state and empty stack are more powerful than those that accept by terminal state alone. This contrasts with the case of stack-counter automata, for which both methods are equally powerful.