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.
Text
min_spec_number_2022_05_21-rev.pdf - Author Accepted Manuscript Download (389kB) | Preview |
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: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3156909 |