No label defined (Q3989948)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 35424
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 35424 |
Statements
28 June 1992
0 references
parallel computation
0 references
cellular automaton on an unbounded binary tree
0 references
polynomial time languages
0 references
0.7647232413291931
0 references
0.7644574642181396
0 references
0.762631356716156
0 references
It seems that a very natural and general model of parallel computation is that of a cellular automaton on an unbounded binary tree. In other words, the memory cells are the vertices of such a tree, and every letter at every vertex is simultaneously updated by a uniform rule on account of itself and of its neighbours. This appears to be a very powerful device since, if we input a word on some path of such a tree then, after time \(t\), the computation affects \(c^ t\) memory cells. Therefore it may be of some interest to study the class of polynomial time languages definable by such machines (which are allowed to use an alphabet extending the original alphabet of the language). This class will be denoted \({\mathbf P}(D_ 3)\). Our main result tells that \[ {\mathbf P}(D_ 3)= {\mathbf{PSPACE}}. \] In some sense this can be viewed as a mathematical proof of the Parallel Computation Thesis of Peter van Emde Boas.
0 references