Characterization of all optimal networks for a simultaneous computation of AND and NOR
type: Item
instance of: scholarly article
title: Characterization of all optimal networks for a simultaneous computation of AND and NOR
zbMATH Open document ID: 0543.94016
DOI: 10.1007/BF00289238
author: Norbert Blum
author: Martin Seysen
published in: Acta Informatica
publication date: 1984-01-01T00:00:00Z
review text: It is proved that the optimal networks (combinational circuits) realizing simultaneously the conjunctions: \(x_ 1x_ 2...x_ n\) (AND function) and \(\bar x_ 1\bar x_ 2...\bar x_ n\) (NOR function) by means of 2- input gates of any possible type consist of the disjoint union of two optimal networks realizing independently the AND and NOR function, respectively.
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 3865154
zbMATH Keywords: simultaneous computation of AND and NOR
zbMATH Keywords: combinational circuits
zbMATH Keywords: AND function
zbMATH Keywords: NOR function
MaRDI profile type: Publication
cites work: A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
cites work: Realizing Boolean functions on disjoint sets of variables
cites work: Relations Among Complexity Measures
cites work: Computational Work and Time on Finite Machines
cites work: The network complexity and the Turing machine complexity of finite functions
cites work: The combinational complexity of equivalence
full work available at URL: https://doi.org/10.1007/bf00289238
OpenAlex ID: W2018363637
description: scientific article; zbMATH DE number 3865154