• DocumentCode
    1147973
  • Title

    Symmetric and Threshold Boolean Functions Are Exhaustive

  • Author

    Moret, Bernard M E ; Thomason, Michael G. ; Gonzalez, Rafael C.

  • Author_Institution
    Department of Computer Science, University of New Mexico
  • Issue
    12
  • fYear
    1983
  • Firstpage
    1211
  • Lastpage
    1212
  • Abstract
    The worst-case number of variable evaluations (testing cost) of Boolean functions is examined. Following up on a result by Rivest and Vuillemin, we show that all symmetric as well as all linearly separable Boolean functions are exhaustive, that is, have a pessimal worst-case testing cost.
  • Keywords
    Argument complexity; decision tree; multiplexer tree; threshold function; worst-case testing cost; Algorithm design and analysis; Boolean functions; Computer science; Cost function; Decision trees; Logic design; Multiplexing; Pattern analysis; Pattern recognition; Testing; Argument complexity; decision tree; multiplexer tree; threshold function; worst-case testing cost;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1983.1676189
  • Filename
    1676189
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1147973