Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functionsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 17 апреля 2024 г.
Аннотация:Abstract—The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into account. The nonmonotone complexity of an arbitraryk-valued logic function is determined with high accuracy, namely, upper and lower bounds whichdiffer by a constant not exceeding 3 log2 k + 4 are found.DOI: 10.1134/S0001434623050218Keywords: multi-valued logic function, logic circuit, circuit complexity, bases with zero weightelements, nonmonotone complexity, inversion complexity, Markov’s theorem