Conference paper

Publication year: 2005

Pages: 311-324

Journal: Theoretical Computer Science

Volume number: 330

Issue number: 2

ISSN: 0304-3975

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2004.04.013

Conference: 4th International Conference on Electromagnetic Wave Interaction with Water and Moist Substances

Publisher: Elsevier

Abstract: 
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 greater than or equal to 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 greater than or equal to 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 greater than or equal to 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. (C) 2004 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M. (2005) On the descriptional power of heads, counters, and pebbles, Theoretical Computer Science, 330(2), pp. 311-324. https://doi.org/10.1016/j.tcs.2004.04.013

APA Citation style: Kutrib, M. (2005). On the descriptional power of heads, counters, and pebbles. Theoretical Computer Science. 330(2), 311-324. https://doi.org/10.1016/j.tcs.2004.04.013