A note on alternating on-line Turing machines (Q789181): Difference between revisions

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

zbMATH Keywords

on-line Turing machines

0 references

alternation

0 references

parallel computation

0 references

reviewed by

U. Klemm

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0020-0190(82)90098-9

0 references

cites work

Alternation

0 references

Tree-size bounded alternation

0 references

On alternation

0 references

On alternation. II. A graph theoretic approach to determinism versus nondeterminism

0 references

Q5636862

0 references

Some Results on Tape-Bounded Turing Machines

0 references

Q5592246

0 references

Identifiers

zbMATH Open document ID

0532.68054

0 references

DOI

10.1016/0020-0190(82)90098-9

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:789181

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0020-0190(82)90098-9
+Normal rank
@@ Property / OpenAlex ID @@
+W1993779423
@@ Property / OpenAlex ID: W1993779423 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Tree-size bounded alternation
@@ Property / cites work: Tree-size bounded alternation / rank @@
+Normal rank
@@ Property / cites work @@
+On alternation
@@ Property / cites work: On alternation / rank @@
+Normal rank
@@ Property / cites work @@
+On alternation. II. A graph theoretic approach to determinism versus nondeterminism
+Normal rank
@@ Property / cites work @@
+Q5636862
@@ Property / cites work: Q5636862 / rank @@
+Normal rank
@@ Property / cites work @@
+Some Results on Tape-Bounded Turing Machines
@@ Property / cites work: Some Results on Tape-Bounded Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank