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

      0 references
      0 references
      28 June 1992
      0 references
      parallel computation
      0 references
      cellular automaton on an unbounded binary tree
      0 references
      polynomial time languages
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references