Bounded Counter Languages

Holger Petersen

doi:10.1007/978-3-642-31623-4_21

paper

Bounded Counter Languages

arXiv:1204.0833 · doi:10.1007/978-3-642-31623-4_21

Abstract

We show that deterministic finite automata equipped with $k$ two-way heads are equivalent to deterministic machines with a single two-way input head and $k - 1$ linearly bounded counters if the accepted language is strictly bounded, i.e., a subset of $a_{1}^{*} a_{2}^{*} ... a_{m}^{*}$ for a fixed sequence of symbols $a_{1}, a_{2}, ..., a_{m}$ . Then we investigate linear speed-up for counter machines. Lower and upper time bounds for concrete recognition problems are shown, implying that in general linear speed-up does not hold for counter machines. For bounded languages we develop a technique for speeding up computations by any constant factor at the expense of adding a fixed number of counters.

References in corpus (1)

Quantum counter automata