Notes on Hazard-Free Circuits

DOI10.1137/20M1355240zbMath1476.68084arXiv2012.10976MaRDI QIDQ4986809

Stasys P. Jukna

Publication date: 28 April 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.10976

zbMATH Keywords

monotone circuitslower boundsShannon functionhazard-free circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• The ellipsoid method and its consequences in combinatorial optimization
• The complexity of partial derivatives
• The gap between monotone and non-monotone circuit complexity is exponential
• On the complexity of detecting hazards
• A Way to Simplify Truth Functions
• A logic hazard detection and elimination method
• Monotone circuits for matching require linear depth
• On the Complexity of Hazard-free Circuits
• Hazard Detection in Combinational and Sequential Switching Circuits
• Application of Ternary Algebra to the Study of Static Hazards
• Elimination of static and dynamic hazards for multiple input changes in combinational switching circuits
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Notes on Hazard-Free Circuits