Konferenzpaper

Jahr der Veröffentlichung: 2005

Seiten: 311-324

Zeitschrift: Theoretical Computer Science

Bandnummer: 330

Heftnummer: 2

ISSN: 0304-3975

Open Access Status: Bronze

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

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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