×

On the planar monotone computation of Boolean functions. (English) Zbl 0637.94023

Summary: A criterion for testing whether a given monotone Boolean function f is planar monotone computable from the sequence of inputs \(x_ 1,x_ 2,...,x_ n\) is developed in conjuction with an algorithm which (in principle) can construct a planar monotone circuit for f whenever one exists. Both the algorithm and the criterion require precomputation of the prime implicants and clauses of f.
As an application of the theory, it is shown that monotone Boolean functions whose prime implicants and clauses contain configurations of a particular type cannot be computed by planar monotone circuits. Moreover, a monotone Boolean function of n inputs which is computable by a planar monotone circuit can be computed by a planar monotone circuit with (1/6)n \(4+O(n\) 3) gates. All monotone Boolean functions on four (or fewer) inputs are shown to be planar monotone computable.

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beynon, W. M., Replaceability and computational equivalence for monotone boolean functions, Acta Inform., 22, 433-449 (1985) · Zbl 0545.94022
[2] Beynon, W. M., Replacement in monotone boolean networks: an algebraic perspective, (Proc. FST&TCS4. Proc. FST&TCS4, Bangalore, 1984. Proc. FST&TCS4. Proc. FST&TCS4, Bangalore, 1984, Lecture Notes in Computer Science, 181 (1984), Springer: Springer Berlin), 165-178
[3] Dunne, P. E., Some results on replacement rules in monotone boolean networks, (Theory of Computation Report 64 (1984), University of Warwick)
[4] McColl, W. F., On the planar monotone computation of threshold functions, (Proc. 2nd STACS. Proc. 2nd STACS, Saarbucken, 1985. Proc. 2nd STACS. Proc. 2nd STACS, Saarbucken, 1985, Lecture Notes in Computer Science, 182 (1985), Springer: Springer Berlin), 219-230 · Zbl 0567.94016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.