scientific article; zbMATH DE number 35424

From MaRDI portal
Publication:3989948





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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989948)