One-Turn Regulated Pushdown Automata and Their Reduction

Abstract

This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final state, and acceptance by empty pushdown.