Negation-limited complexity of parity and inverters

DOI10.1007/s00453-007-9135-1zbMath1200.94063OpenAlexW2614435365MaRDI QIDQ1022345

Jun Tarui, Kazuo Iwama, Hiroki Morizumi

Publication date: 22 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9135-1

zbMATH Keywords

circuit complexityparity functioninversion complexityinverternegation-limited circuitgate elimination

Mathematics Subject Classification ID

Analytic circuit theory (94C05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Negation-limited circuit complexity of symmetric functions
• On the negation-limited circuit complexity of merging
• Higher lower bounds on monotone size
• On the Inversion Complexity of a System of Functions
• On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences
• On the Complexity of Negation-Limited Boolean Networks
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

This page was built for publication: Negation-limited complexity of parity and inverters