Simulations by Time-Bounded Counter Machines

Holger Petersen

Abstract:
We investigate the efficiency of simulations of storages by several
counters.  A simulation of a pushdown store is described which is
optimal in the sense that reducing the number of counters of a
simulator leads to an increase in time complexity. The lower bound
also establishes a tight counter hierarchy in exponential time. Then
we turn to simulations of a set of counters by a different number of
counters. We improve and generalize a known simulation in polynomial
time and we show a tight hierarchy result for machines working in the
same polynomial bound with an increasing number of counters. We also
prove hierarchies for machines with a fixed number of counters and
with growing polynomial time bounds.