A note on alternating on-line Turing machines
type: Item
instance of: scholarly article
title: A note on alternating on-line Turing machines
zbMATH Open document ID: 0532.68054
DOI: 10.1016/0020-0190(82)90098-9
author: Katsushi Inoue
author: Itsuo Takanami
author: Hiroshi Taniguchi
published in: Information Processing Letters
publication date: 1982-01-01T00:00:00Z
review text: Die Verf. verfeinern die bekannte Klasse der speicherplatzbeschränkten AN1TM (alternierende nondeterministische 1-Leserichtungs-Turingmaschinen) durch das Resourcenmaß ''Blattgröße'' in eine neue hierarchische Familie. Unter ''Blattgröße'' verstehen die Verf. (eine Schranke für) die minimale Anzahl der Endpunkte des Arbeitsbaumes (computation tree), wenn das Eingabewort akzeptiert wird; mit anderen Worten die minimale Anzahl der dabei zuletzt simultan aktiven Prozessoren.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3845057
zbMATH Keywords: on-line Turing machines
zbMATH Keywords: alternation
zbMATH Keywords: parallel computation
reviewed by: U. Klemm
MaRDI profile type: Publication
full work available at URL: 0020-0190(82)90098-9
OpenAlex ID: W1993779423
cites work: Alternation
cites work: Tree-size bounded alternation
cites work: On alternation
cites work: On alternation. II. A graph theoretic approach to determinism versus nondeterminism
cites work: Q5636862
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q5592246
Recommended article: Alternating on-line Turing machines with only universal states and small space bounds
Recommended article: On reversal bounded alternating Turing machines
Recommended article: A note on accelerated Turing machines
Recommended article: On alternating \(\omega\)-automata
Recommended article: A note on alternating one-pebble Turing machines with sublogarithmic space
Recommended article: A remark on middle space bounded alternating Turing machines
Recommended article: Some observations concerning alternating Turing machines using small space
Recommended article: A NOTE ON REBOUND TURING MACHINES
Recommended article: The complexity of on-line simulations between multidimensional turing machines and random access machines
Recommended article: On space-bounded synchronized alternating Turing machines
description: scientific article; zbMATH DE number 3845057