On the complexity of multivalued logic functions over some infinite basis

DOI10.1134/S1990478918010052MaRDI QIDQ4553643zbMATH OpenOpenAlexWikidataFDO

Authors Vadim V. Kochergin, Anna Vital'evna Mikhailovich

Publication date 30 October 2018

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

inversion complexitylogic circuitinfinite basismulti-valued logic function

Mathematics Subject Classification ID

Recommendations

• Circuit complexity of \(k\)-valued logic functions in one infinite basis
• Depth of functions of the \(k\)-valued logic in infinite bases
• Complexity of implementing functions of k-valued logic by circuits and formulas in functionally complete bases
• Depth of functions of \(k\)-valued logic in finite bases
• On the depth of \(k\)-valued logic functions over arbitrary bases

Cites work

• scientific article; zbMATH DE number 3130282 (Why is no real title available?)
• scientific article; zbMATH DE number 3513337 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 3273218 (Why is no real title available?)
• scientific article; zbMATH DE number 3319974 (Why is no real title available?)
• scientific article; zbMATH DE number 3348015 (Why is no real title available?)
• scientific article; zbMATH DE number 3419055 (Why is no real title available?)
• Algorithms and Computation
• Boolean function complexity. Advances and frontiers.
• Circuit complexity of symmetric Boolean functions in antichain basis
• Lattice Theoretic Properties of Frontal Switching Functions
• Learning circuits with few negations
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• On the complexity of schemes in an infinite basis
• Orders of growth of Shannon functions for circuit complexity over infinite bases
• Some properties of Shannon functions
• The minimum number of edges in graphs with prescribed paths
• The minimum number of negations in circuits for systems of multi-valued functions
• The power of negations in cryptography

Cited in

(11)

• Circuit complexity of \(k\)-valued logic functions in one infinite basis
• A sequence of functions of the multi-valued logic
• The minimum number of negations in circuits for systems of multi-valued functions
• ON LOWER BOUNDS FOR COMPLEXITY OVER INFINITE BASISES FOR FUNCTIONS OF MULTI-VALUED LOGIC
• Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions
• scientific article; zbMATH DE number 5005220 (Why is no real title available?)
• Complexity of implementing functions of k-valued logic by circuits and formulas in functionally complete bases
• Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
• Complexity of functions from some classes of three-valued logic
• Depth of functions of the \(k\)-valued logic in infinite bases
• On the depth of \(k\)-valued logic functions over arbitrary bases

This page was built for publication: On the complexity of multivalued logic functions over some infinite basis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4553643)