A note on alternating on-line Turing machines (Q789181)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on alternating on-line Turing machines |
scientific article; zbMATH DE number 3845057
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on alternating on-line Turing machines |
scientific article; zbMATH DE number 3845057 |
Statements
A note on alternating on-line Turing machines (English)
0 references
1982
0 references
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.
0 references
on-line Turing machines
0 references
alternation
0 references
parallel computation
0 references
0.9059906
0 references
0.8618317
0 references
0 references
0 references
0 references
0.85658866
0 references
0.85137737
0 references
0 references
0.8482719
0 references
0.84821594
0 references
