One-Turn Regulated Pushdown Automata and Their Reduction

Article type: Research Article

Authors: Meduna, Alexander | Kolář, Dušan

Affiliations: Brno University of Technology, Department of Computer Science and Engineering, Božetěchova 2, Brno 612 66, Czech Republic

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.

Keywords: one-turn regulated pushdown automata, reduced and atomic variants, recursively enumerable languages

Journal: Fundamenta Informaticae, vol. 51, no. 4, pp. 399-405, 2002