Limiting negations in bounded-depth circuits: An extension of Markov's theorem

A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bound...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2004-04, Vol.90 (1), p.15-20
Main Authors: Sung, Shao Chin, Tanaka, Keisuke
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Boolean
Circuit complexity
Combinatorics. Ordered structures
Computational complexity
Computer science
Computer science
control theory
systems
Exact sciences and technology
Information retrieval
Integrated circuits
Markov analysis
Mathematics
Negation-limited circuits
Order, lattices, ordered algebraic structures
Sciences and techniques of general use
Studies
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2004.01.003