On the descriptional power of heads, counters, and pebbles

We investigate the descriptional complexity of deterministic two-way k-head finite automata (k-DHA). It is shown that between non-deterministic pushdown automata and any k-DHA, k⩾2, there are savings in the size of description which cannot be bounded by any recursive function. The same is true for the other end of the hierarchy. Such non-recursive trade-offs are also shown between any k-DHA, k⩾1, and DSPACE(log)=multi-DHA. We also address the particular case of unary languages. In general, it is possible that non-recursive trade-offs for arbitrary languages reduce to recursive trade-offs for unary languages. Here we present huge lower bounds for the unary trade-offs between non-deterministic finite automata and any k-DHA, k⩾2. Furthermore, several known simulation results imply the presented trade-offs for other descriptional systems, e.g., deterministic two-way finite automata with k pebbles or with k linearly bounded counters.