This article is cited in
2 papers
On the complexity of the sequential realization of partial Boolean functions by schemes
L. A. Sholomov Institute of Systems Analysis, Russian Academy of Sciences
Abstract:
A pair
$(f,g)$ of partial Boolean functions is characterized by a tuple of parameters
$l_{\alpha\beta}$ that is the number of tuples
$\tilde x$ such that
$(f(\tilde x),g(\tilde x))=(\alpha,\beta)$, where
$\alpha$ and
$\beta$ take the values 0, 1, and an undefined value. The sequential computation of
$(f,g)$ is considered when a circuit
$S_f$ for
$f$ is constructed first, and, next, it is completed by the construction up to a circuit
$S_{f,g}$. It is shown that if the domain
$D(f)$ includes
$D(g)$ then it is possible to compute sequentially
$f$ and
$g$ in such a way that
$S_f$ and
$S_{f,g}$ are asymptotically minimal simultaneously (i.e., they satisfy the asymptotically best bounds on the complexity for corresponding classes); and, in general, these functions cannot be sequentially computed in the order
$g$,
$f$ so that
$S_g$ and
$S_{f,g}$ are asymptotically minimal. An attainable lower bound is obtained on the size of the circuit
$S_{f,g}$ for the sequential computation. The information properties of partially defined data play an essential role whose study in the previous papers of the author is continued here.
Fulltext:
PDF file (365 kB)