Models of pushdown automata with reset

Nuri Taşdemir and A.C. Cem Say

Abstract. We examine various pushdown automaton variants that are architecturally intermediate between the one-way PDA and the two-way PDA (2PDA), where leftward moves of the input head can only reset it to the left end of the tape, and some component of the machine configuration may be “forgotten”, that is, reset to its initial value, whenever such a move is performed. Most of these model variants are shown to be equivalent in power to either the 2PDA or the one-way PDA. One exception is the Resettable Pushdown Automaton (RPDA), where the stack contents are lost every time the input is reset, and which we prove to be intermediate in power between the PDA and the 2PDA. We give full characterizations of the classes of languages recognized by both the deterministic and the nondeterministic versions of the RPDA.

Comments are closed.