Pushdown automata with counters

✍ Scribed by T. Kameda

• Book ID: 104148074
• Publisher: Elsevier Science
• Year: 1972
• Tongue: English
• Weight: 576 KB
• Volume: 6
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(72)80019-9

✦ Synopsis

The computational power of 2-way pushdown acceptors with m(~> 1) additional counters (called mC-PDA) is investigated. It is shown that given any multitape Turing machine M that accepts within time T(n), where n is the input length, one can find a 3C-PDA M' such that M and M' accept the same set of inputs and if M accepts an input w of length n within time T(n), then M' accepts w storing no more than count T(n) in any of the counters. For any such Turing machine, one can also find a 2C-PDA which accepts the same set within count T(n) 2.

A number of other results relating the power of 1C-PDA and those of other types of acceptors are also obtained.