On the construction of parallel computers from various basis of Boolean functions
type: Item
instance of: scholarly article
title: On the construction of parallel computers from various basis of Boolean functions
zbMATH Open document ID: 0604.68054
DOI: 10.1016/0304-3975(86)90165-9
author: Leslie M. Goldschlager
author: Ian Parberry
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: At first the space complexity of the circuit value problem (CVP) over two-input bases is studied. It is found out that, for the two-input bases B, either \(CVP_ B\) is log space complete for P, or it can be computed in \(O(\log^ 2n)\) space. After that, the extended Turing machine (ETM) is introduced and it is proved that the ETM over two-input Boolean bases B are as powerful as parallel machines iff the CVP over basis B is log space complete for P. The case of ETM with domain \(D=\{0,1\}\) and basis \(B\subseteq B_ 2\) is studied in more detail. Networks over basis B are considered. To eliminate NOT gates, the idea of ''double rail logic'' is used. A particular basis \(B\subseteq B_ 2\) can be used to build general purpose machines iff B is P-complete. The conditions for that are proved. It appears that \(\{\wedge,\vee \}\) is not a powerful computational basis for planar circuits.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 3976340
zbMATH Keywords: parallel computation
zbMATH Keywords: space complexity
zbMATH Keywords: circuit value problem
zbMATH Keywords: extended Turing machine
zbMATH Keywords: parallel machines
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90165-9
OpenAlex ID: W2094404282
cites work: On the computational power of pushdown automata
cites work: Alternation
cites work: Q4138187
cites work: Q4198056
cites work: Q4128417
cites work: A space efficient algorithm for the monotone planar circuit value problem
cites work: A universal interconnection pattern for parallel computers
cites work: Complete problems for deterministic polynomial time
cites work: Q4142699
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Computational Work and Time on Finite Machines
cites work: The Complexity of Enumeration and Reliability Problems
description: scientific article; zbMATH DE number 3976340