Meng-Jing Li, Yu-Chuan Yen, Yi-Ting Li, Yung-Chih Chen, Chun-Yao Wang

A Constructive Approach for Threshold Function Identification

  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design
  • Computer Science Applications

Threshold Function (TF) is a subset of Boolean function that can be represented with a single linear threshold gate (LTG). In the research about threshold logic, the identification of TF is an important task that determines whether a given function is a TF or not. In this article, we propose a sufficient and necessary condition for a function being a TF. With the proposed sufficient and necessary condition, we devise a TF identification algorithm. The experimental results show that the proposed approach saves 80% CPU time for identifying all the 8-input NP-class TFs as compared with the state-of-the-art. Furthermore, the LTGs corresponding to the identified TFs obtained by the proposed approach have smaller weights and threshold values than the state-of-the-art.

Need a simple solution for managing your BibTeX entries? Explore CiteDrive!

  • Web-based, modern reference management
  • Collaborate and share with fellow researchers
  • Integration with Overleaf
  • Comprehensive BibTeX/BibLaTeX support
  • Save articles and websites directly from your browser
  • Search for new articles from a database of tens of millions of references
Try out CiteDrive

More from our Archive