Small Hazard-Free Transducers
summary
Claims that every Mealy transducer on n inputs admits a hazard-free circuit of size O(n · 2^{|S|+e}) and depth O(|S| log n + e) where |S| is state count and e is input-encoding size, built by adapting Lauter Fisher parallel-prefix composition and using state-subset transition matrices that record transitions for every subset to avoid information loss under u inputs. Construction yields logarithmic depth for constant |S| and e. Application to addition uses a unary+Gray encoding and assumes bounded uncertainty; circuits are explicit though constants may be large.
AI-written summary · about