Logic and complexity of synchronous parallel computations

Show full item record

Title: Logic and complexity of synchronous parallel computations
Author: Radziszowski, Stanislaw
Abstract: We investigate a certain model of synchronous parallelism. Syntax, semantics and complexity of programs within it are defined. We consider algorithmic properties of synchronous parallel programs in connection with sequential programs with arrays. The complexity theorem states that the class PP-time (polynomial-time bounded parallel languages) is equal to P-space (languages requiring polynomial amount of memory).
Record URI: http://hdl.handle.net/1850/9812
Date: 1978

Files in this item

Files Size Format View
SRadziszowskiArticle1978.pdf 6.475Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse