On the complexity of hazard-free circuits

DOI10.1145/3188745.3188912MaRDI QIDQ5230345zbMATH OpenOpenAlexFDO

Authors Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Andrey Mokhov, Karteek Sreenivasaiah, Vladimir Lysikov

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://eprint.ncl.ac.uk/fulltext.aspx?url=260552/A42C0751-2F49-4FC4-A113-713C1C9C0F85.pdf&pub_id=260552

zbMATH Keywords

Boolean circuitscomputational complexityhazardsmonotone circuits

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of hazard-free circuits
• On the complexity of circuit satisfiability
• scientific article; zbMATH DE number 3963737
• scientific article; zbMATH DE number 3478767
• Notes on hazard-free circuits
• On the complexity of detecting hazards
• The Complexity of Fault Detection Problems for Combinational Logic Circuits
• On the Numerical Complexity of Short-Circuit Faults in Logic Networks
• Optimal design of hazard-free and easily testable logic networks
• On the complexity of worst case and expected time in a circuit

Cited in

(4)

• On the complexity of detecting hazards
• Optimal design of hazard-free and easily testable logic networks
• Notes on hazard-free circuits
• On the complexity of hazard-free circuits

This page was built for publication: On the complexity of hazard-free circuits

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