Pushdown automata with counters

摘要

The computational power of 2-way pushodown 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.