ON LOWER BOUNDS FOR COMPLEXITY OVER INFINITE BASISES FOR FUNCTIONS OF MULTI-VALUED LOGIC

DOI10.17223/20710410/29/1OpenAlexW4244923260MaRDI QIDQ5150696

A. A. Andreev

Publication date: 15 February 2021

Published in: PRIKLADNAYa DISKRETNAYa MATEMATIKA (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm511

zbMATH Keywords

exponential depth boundsfunctions of multi-valued logicincomplete basisesinfinite basisesoverexponential complexity bounds

Mathematics Subject Classification ID

Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth of functions of \(k\)-valued logic in finite bases
• General upper bound of circuit complexity in an arbitrary infinite complete base
• Lower complexity estimates for some sequences of functions of multivalued logic
• Depth of functions of the \(k\)-valued logic in infinite bases
• A sequence of functions of the multi-valued logic