Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions

DOI10.1134/s0001434623050218zbMath1527.94097OpenAlexW4381331236MaRDI QIDQ6114318

Anna Vital'evna Mikhailovich, Vadim V. Kochergin

Publication date: 11 July 2023

Published in: Mathematical Notes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0001434623050218

zbMATH Keywords

circuit complexityMarkov's theoreminversion complexitylogic circuitbases with zero weight elementsnonmonotone complexitymulti-valued logic function

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
• The minimum number of negations in circuits for systems of multi-valued functions
• Exact value of the nonmonotone complexity of Boolean functions
• Circuit complexity of \(k\)-valued logic functions in one infinite basis
• On the Inversion Complexity of a System of Functions
• On the Complexity of Multivalued Logic Functions over Some Infinite Basis
• Lattice Theoretic Properties of Frontal Switching Functions

This page was built for publication: Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions