The minimum number of negations in circuits for systems of multi-valued functions

DOI10.1515/dma-2017-0030zbMath1441.94117OpenAlexW2763840267MaRDI QIDQ1744290

Vadim V. Kochergin, Anna Vital'evna Mikhailovich

Publication date: 23 April 2018

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2017-0030

zbMATH Keywords

logic circuitscircuit complexityMarkov's theoreminversion complexitymulti-valued logic functionsnonmonotone complexity

Mathematics Subject Classification ID

Many-valued logic (03B50) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items (4)

On the Complexity of Multivalued Logic Functions over Some Infinite Basis ⋮ Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions ⋮ Exact value of the nonmonotone complexity of Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Negation-limited circuit complexity of symmetric functions
• On the Inversion Complexity of a System of Functions
• Negation-Limited Inverters of Linear Size
• Limiting Negations in Formulas
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• Algorithms and Computation
• The Power of Negations in Cryptography
• Learning circuits with few negations
• Lattice Theoretic Properties of Frontal Switching Functions

This page was built for publication: The minimum number of negations in circuits for systems of multi-valued functions