Complexity of self-correcting circuits for some sequence of Boolean functions

k-Self-correcting circuits of functional elements in the basis {x ₁&x ₂, $ \bar x $ \bar x } are considered. It is assumed that constant faults on outputs of functional elements are of the same type. Inverters are supposed to be reliable in service. The weight of each inverter is equal to 1. Conjunctors can be reliable in service, or not reliable. Each reliable conjunctor implements a conjunction of two variables and has a weight p > k + 2. Each unreliable conjunctor implements a conjunction in its correct state and implements a Boolean constant δ (δ ∈ {0, 1}) otherwise. Each unreliable conjunctor has the weight 1. It is stated that the complexity of realization of monotone threshold symmetric functions $ f_2^n \left( {x_1 ,...,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_1 x_j ,n = 3,4 $ f_2^n \left( {x_1 ,...,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_1 x_j ,n = 3,4 , ... by such circuits asymptotically equals (k + 3)n.     

Remark on minimization of depth of Boolean circuits

It is shown that Lozhkin’s method (1981) for minimization of the depth of formulas with a bounded number of changing types of elements in paths from input to output and Hoover-Klawe-Pippenger’s method (technical report in 1981, journal publication in 1984) for minimization of the depth of circuits with unbounded branching by insertion of trees from buffers with bounded branching of outputs for each buffer are dual to each other and can be proved by one and the same method.     

Diagnostic tests for local coalescences of variables in Boolean functions

The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]ⁿ )( 1 ￡ k ￡ n,  1 ￡ t ￡ 2^2k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions F_t^k \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 ^k (n − k + 1) for n → ∞, k → ∞.     

Single fault detection tests for circuits of functional elements

Circuits of functional elements in arbitrary complete finite bases are considered. The realizability of any Boolean function of n variables by an irredundant circuit admitting single fault detection tests having a length linear in n for constant faults is established.     

Complexity of sequential computations of partial Boolean functions by circuits

A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples $ \tilde x A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples such that (f( ), g( )) = (α, β), where α and β 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. Original Russian Text ? L.A. Sholomov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14, No. 1, pp. 110–139.     

Local negative circuits and fixed points in non-expansive Boolean networks

Given a Boolean function F:{0,1}ⁿ→{0,1}ⁿ, and a point x in {0,1}ⁿ, we represent the discrete Jacobian matrix of F at point x by a signed directed graph G_F(x). We then focus on the following open problem: Is the absence of a negative circuit in G_F(x) for every x in {0,1}ⁿ a sufficient condition for F to have at least one fixed point? As result, we give a positive answer to this question under the additional condition that F is non-expansive with respect to the Hamming distance.     

Realization of Boolean functions by combinational circuits embedded in the hypercube

In recent years, it has become popular to realize Boolean functions by combinational circuits. In many cases, the further use of the scheme constructed requires its geometric realization, i.e., a certain embedding in one or another specific geometric structure. The role of such structure is often played by the unit n-dimensional cube.In this paper, we consider quasihomeomorphic embeddings of combinational circuits in hypercubes such that the nodes of the scheme go into vertices of the hypercube and bundles of arcs go into similar bundles or the so-called transition trees of the hypercube having no common internal vertices.

Let B be a finite complete basis of functional elements and R _B(n) be the minimum dimension of a hypercube such that, for any function f(x ₁, …, x _n ) of Boolean logic, there is a certain scheme of functional elements in basis B realizing f(x ₁, …, x _n ) which can be quasihomeomorphically embedded in this cube. The main result of this work consists in derivation of the following estimates:

$n - \log \log (n) - c_B \leqslant R_B (n) \leqslant n - \log \log (n) + c'_B .$

Here, c _B and c′_B are basis-dependent constants.     

Depth of Boolean functions realized by circuits over an arbitrary infinite basis

Bounds for the circuit depth of all Boolean functions tight up to a small additive constant are obtained for all infinite bases.     

The depth of Boolean functions realized by circuits over an arbitrary basis

Realization of Boolean functions by circuits of functional elements is considered over arbitrary complete bases (including infinite ones). The depth of a circuit means the maximal number of functional elements forming an oriented chain going from inputs of the circuit to its output. It is shown that for any basis B the growth order of the Shannon function of depth D _B (n) for n → ∞ is equal to 1, log₂ n, or n, and the latter case appears if and only if the basis B is finite.     

Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type

D. M. Barrington proved the coincidence of the class NC¹ of functions computable by the circuits of logarithmic depth with the class of functions computable by branching programs of constant width and polynomial length (BWBP). In this paper, the structure of branching programs suggested by the Barrington method is defined more exactly. Namely, it is proved that we can compute all functions from NC¹ and only them by the k-OBDDs of polynomial size and width 5. This can be reformulated as poly(n)-OBDD₅ =NC¹.     

Complexity of realization of Boolean functions with small number of unit values by selfcorrecting contact circuits

An asymptotics for the complexity of realization of Boolean functions taking the unit value on a comparatively small set of collections of variables by self-correcting contact circuits is obtained.     

Boolean distance for graphs

The boolean distance between two points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (Ø if x = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x,y)? b(x, z)∪b(z,y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together with the number of occurrences of each of them. Then $\text{B(G)}\text{= 1+(}{}^{\mathrm{b+1}}{}_2\text{)}$ where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.     

More constructions for Boolean algebras

 We construct Boolean algebras with prescribed behaviour concerning depth for the free product of two Boolean algebras over a third, in ZFC using pcf; assuming squares we get results on ultraproducts. We also deal with the family of cardinalities and topological density of homomorphic images of Boolean algebras (you can translate it to topology - on the cardinalities of closed subspaces); and lastly we deal with inequalities between cardinal invariants, mainly . Received: 9 September 1998 / Published online: 7 May 2002     

A method for synthesis of easily-testable circuits in some basis admitting single fault detection tests of constant length

A method of synthesis of irredundant circuits of functional elements in the basis {x&y, x??y, 1, $\bar x$ (y ?? z) ?? x(y ?? z)} realizing arbitrary Boolean functions and admitting unit verification tests of the length not exceeding 4 is proposed in the paper for inverse or constant (stuck-at) faults at outputs of gates.     

Annihilator characterizations of Boolean rings and Boolean lattices

Translated from Matematicheskie Zametki, Vol. 53, No. 2, pp. 15–24, February, 1993.