A note on alternating on-line Turing machines (Q789181): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Property / reviewed by | |||
| Property / reviewed by: U. Klemm / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: U. Klemm / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(82)90098-9 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1993779423 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Alternation / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Tree-size bounded alternation / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On alternation / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On alternation. II. A graph theoretic approach to determinism versus nondeterminism / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5636862 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Some Results on Tape-Bounded Turing Machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Latest revision as of 11:56, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on alternating on-line Turing machines |
scientific article |
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
