Remarks on two-way automata with weak-counters
type: Item
instance of: scholarly article
title: Remarks on two-way automata with weak-counters
zbMATH Open document ID: 0538.68049
DOI: 10.1016/0020-0190(84)90032-2
author: Satoru Miyano
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: A counter which stores any nonnegative integer has three kinds of operations: add, subtract and zero test. The weak-counter is defined as a counter that cannot be tested for zero. Machines with multiple weak- counters have received considerable attention from several points. This paper gives some observations on two-way automata with weak-counters. Two-way finite, pushdown and stack automata are well-known examples of two-way automata. First the author investigates how additional weak- counters affect the recognition power of these automata. It is proved that such deterministic automata augmented with one weak-counter have the same recognition ability as those with k weak-counters for all \(k\geq 1\). Second he shows that any two-way nondeterministic one-weak-counter machine can be simulated by a two-way three-counter machine which accepts in linear time. As a corollary of this fact, it is proved that the language \(\{ww^ R| w\quad is\quad in\quad \{0,1\}^*\}\) cannot be recognized by any two-way nondeterministic one-weak-counter machine although this language is recognizable by a two-way deterministic one- counter machine.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3856421
zbMATH Keywords: weak-counter automata
zbMATH Keywords: two-way automata
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90032-2
OpenAlex ID: W1965194891
cites work: Counter machines and counter languages
cites work: Remarks on blind and partially blind one-way multicounter machines
cites work: Q4190159
cites work: Two-way deterministic multi-weak-counter machines
cites work: Relationships between pushdown automata with counters and complexity classes
description: scientific article; zbMATH DE number 3856421