One-Turn Regulated Pushdown Automata and Their Reduction

• Autorzy: Meduna A. , Kolar D.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

one-turn regulated pushdown automata; reduced and atomic variants; recursively enumerable languages

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 51, nr 4
• Strony: 399--405
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Meduna A.

autor

Kolar D.

• Department of Computer Science and Engineering Brno University of Technology Bozetechova 2 Brno 61266, Czech Republic,