On the Descriptional Power of Heads, Counters, and Pebbles.
Martin Kutrib · DCFS · 2003
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.