On Boolean threshold functions with minimum specification number

Lozin, Vadim, Zamaraev, Viktor ORCID: 0000-0001-5755-4141, Zamaraeva, Elena and Zolotykh, Nikolai Yu (2022) On Boolean threshold functions with minimum specification number. INFORMATION AND COMPUTATION, 289. p. 104926.

Access the full-text of this item by clicking on the Open Access link.

Text
min_spec_number_2022_05_21-rev.pdf - Author Accepted Manuscript
Download (389kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ic.2022.104926

Abstract

A set S of Boolean points is a specifying set for a threshold function f if the only threshold function consistent with f on S is f itself. The minimal cardinality of a specifying set for f is the specification number of f and it is never smaller than n+1 for a function with n relevant variables. In the present paper, we develop an inductive approach to describing the set of Boolean threshold functions with minimum specification number by means of operations that allow us to extend functions of n variables in this set to functions of n+1 variables.

Item Type:	Article
Uncontrolled Keywords:	Boolean threshold function, Specification number, Essential points
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	21 Jun 2022 15:12
Last Modified:	22 Feb 2023 13:16
DOI:	10.1016/j.ic.2022.104926
Open Access URL:	https://doi.org/10.1016/j.ic.2022.104926
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3156909