Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Realizing Boolean Functions on Disjoint Sets of Variables

Realizing Boolean Functions on Disjoint Sets of Variables

File(s)
75-215.pdf (890.62 KB)
75-215.ps (344.05 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6996
Collections
Computer Science Technical Reports
Author
Paul, Wolfgang J.
Abstract

For switching functions $f$ let $C(f)$ be the combinatorial complexity of $f$. We prove that for every $\varepsilon greater than 0$ there are arbitrarily complex functions $f:{0,1}^{n} \rightarrow {0,1}^{n}$ such that $C(fxf) \leq (1+ \varepsilon) C(f)$ and arbitrarily complex functions $g:{0,1}$ such that $C(v c(fxf)) \leq (1 + \varepsilon)C(f)$. These results and the techniques developed to obtain them are used to show, that Ashenhurst decomposition of switching functions does not always yield optimal circuits and to prove a new result concerning the trade-off between circuit size and monotone circuit size.

Date Issued
1975-10
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-215
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance