Pushdown automata with reversal-bounded counters

DOI10.1016/0022-0000(88)90008-6zbMath0659.68074OpenAlexW2029408153MaRDI QIDQ1112611

Tat-Hung Chan

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90008-6

zbMATH Keywords

reversal-bounded counterspushdown automatonpushdown storecomputing powersimulation by Turing machines

Mathematics Subject Classification ID

Related Items (2)

On the complexity of decision problems for some classes of machines and applications ⋮ Unboundedness problems for machines with reversal-bounded counters

Cites Work

• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The complexity of decision problems for finite-turn multicounter machines
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Reversal-bounded multipushdown machines
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Pushdown automata with reversal-bounded counters