On pebble automata
type: Item
instance of: scholarly article
title: On pebble automata
zbMATH Open document ID: 0612.68045
DOI: 10.1016/0304-3975(86)90112-X
author: Jik H. Chang
author: Oscar H. Ibarra
author: Michael A. Palis
author: B. Ravikumar
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Steinchen (pebbles) heißen hier sehr bildhaft reversible und kumulierbare Markierungen, die eine Turing-Maschine (TM) auf ihrem Eingabeband anbringen und aufsuchen kann. 1-Steinchen-TM können Probleme in DSPACE(loglog n) bearbeiten; laut \textit{A. R. Freedman} und \textit{R. E. Ladner} [J. Comput. Syst. Sci. 11, 118-128 (1975; Zbl 0307.68036)] ist diese Problemklasse für TM ohne Steinchen verschlossen. Arbeitsplatz unterhalb loglog n ist für 1 Steinchen äquivalent zu konstantem Arbeitsplatz. 2-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie Automaten mit nichtlöschbarem, aber zerstörungsfrei lesbarem Keller. 3-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie 2weg-Kellerautomaten (2DPDA's). Wesentlicher als die Fülle von Einzelergebnissen, die sichtlich der ordnenden Hand des Morphologen (Zwicky) bedürfen, ist die breite Anwendung einer Beweistechnik, die sich der Tiefensuche über dem Baum der Konfigurationen eines deterministischen Automaten bedient [\textit{M. Sipser}, Theor. Comput. Sci. 10, 335-338 (1980; Zbl 0423.68011)].
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3990872
zbMATH Keywords: recognition power
zbMATH Keywords: space-bounded Turing machine
zbMATH Keywords: accepted languages
reviewed by: U. Klemm
MaRDI profile type: Publication
cites work: Time and tape complexity of pushdown automaton languages
cites work: Space bounds for processing contentless inputs
cites work: An Infinite Hierarchy of Context-Free Languages
cites work: Checking automata and one-way stack languages
cites work: On tape bounds for single letter alphabet language processing
cites work: One-tape, off-line Turing machine computations
cites work: Q5592246
cites work: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
cites work: On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
cites work: Language recognition by marking automata
cites work: Q3926078
cites work: Halting space-bounded computations
cites work: Q5636862
description: scientific article; zbMATH DE number 3990872