English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Small Hazard-free Transducers

MPS-Authors
/persons/resource/persons220570

Bund,  Johannes
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons123371

Lenzen,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1811.12369.pdf
(Preprint), 417KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bund, J., Lenzen, C., & Medina, M. (2018). Small Hazard-free Transducers. Retrieved from http://arxiv.org/abs/1811.12369.


Cite as: https://hdl.handle.net/21.11116/0000-0002-9FAD-9
Abstract
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 \emph{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 $\ell$ bits, has a hazard-free circuit of
size $2^{\BO(s+\ell)}\cdot n$ and depth $\BO(\ell+ s\cdot \log n)$; in
particular, if $s, \ell\in \BO(1)$, size and depth are asymptotically optimal.
We utilize our main result to derive efficient circuits for
\emph{$k$-recoverable addition}. Informally speaking, a code is
\emph{$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,\ldots,x+k\}$ for some $x\in \NN_0$. We provide an asymptotically
optimal $k$-recoverable code. We also realize a transducer with $\BO(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^{\BO(k)}n$ and depth
$\BO(k\log 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$.