Small Hazard-free Transducers
share
Recently, an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions has been shown. This raises the question: which classes of functions permit efficient hazard-free circuits? Our main result is as follows. A transducer is a finite state machine that transcribes, symbol by symbol, an input string of length n into an output string of length n. We prove that any function arising from a transducer with s states, that is input symbols which are encoded by ℓ bits, has a hazard-free circuit of size 2^(s+ℓ)· n and depth (ℓ+ s· n); in particular, if s, ℓ∈(1), size and depth are asymptotically optimal. We utilize our main result to derive efficient circuits for k-recoverable addition. Informally speaking, a code is k-recoverable if it does not increase uncertainty regarding the encoded value, so long as it is guaranteed that it is from {x,x+1,...,x+k} for some x∈_0. We provide an asymptotically optimal k-recoverable code. We also realize a transducer with (k) states that adds two codewords from this k-recoverable code. Combined with our main result, we obtain a hazard-free adder circuit of size 2^(k)n and depth (k n) with respect to this code, i.e., a k-recoverable adder circuit that adds two codewords of n bits each. In other words, k-recoverable addition is fixed-parameter tractable with respect to k.
READ FULL TEXT
