Properties of complexity measures for PRAMs and WRAMs
type: Item
instance of: scholarly article
title: Properties of complexity measures for PRAMs and WRAMs
zbMATH Open document ID: 0626.68040
DOI: 10.1016/0304-3975(86)90083-6
author: Siegfried Bublitz
author: Ingo Wegener
author: Ute Schuerfeld
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: The computation of Boolean functions by parallel computers with shared memory (PRAMs and WRAMs) is considered. In particular, complexity measures for parallel computers like critical and sensitive complexity are compared with other complexity measures for Boolean functions like branching program depth and length of prime implicants and clauses. The relations between these complexity measures and their asymptotic behaviour are investigated for the classes of Boolean functions, monotone functions and symmetric functions.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4018388
zbMATH Keywords: computation of Boolean functions
zbMATH Keywords: parallel computers with shared memory
zbMATH Keywords: PRAMs
zbMATH Keywords: WRAMs
zbMATH Keywords: complexity measures for parallel computers
zbMATH Keywords: complexity measures for Boolean functions
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90083-6
OpenAlex ID: W2064007242
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Q3286850
cites work: Q5538132
cites work: Q3779735
cites work: Q4193510
cites work: Q3671891
cites work: On recognizing graph properties from adjacency matrices
cites work: Q3674058
cites work: The critical complexity of graph properties
cites work: Trade-Offs between Depth and Width in Parallel Computation
cites work: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
cites work: The critical complexity of all (monotone) boolean functions and monotone graph properties
description: scientific article; zbMATH DE number 4018388