On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store

DOI10.1016/S0019-9958(82)80023-5zbMath0523.68037MaRDI QIDQ3674059

Pavol Ďuriš, Zvi Galil

Publication date: 1982

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

hierarchypushdown automatareversal-bounded counter machine languagestwo-way machines

Mathematics Subject Classification ID

Related Items (11)

Reversal-bounded nondeterministic multicounter machines and complementation ⋮ On reversal bounded alternating Turing machines ⋮ Tradeoffs for language recognition on alternating machines ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ One-reversal counter machines and multihead automata: revisited ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ New Results on the Minimum Amount of Useful Space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Nondeterministic multicounter machines and complementation ⋮ A characterization of reversal-bounded multipushdown machine languages

This page was built for publication: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store