The asymptotically best method for synthesizing limited-depth Boolean recursive schemes

A model of limited-depth recursive schemes for the functions of Boolean algebra (Boolean functions), constructed from multi-output functional elements, is considered. A lower estimate of the Shannon function for the complexity of schemes of this class is derived. Upper estimates for the complexity of some specific functions and systems of functions in this class of schemes are obtained. A method is proposed for synthesizing schemes of this class for arbitrary functions that allow us (using the derived lower estimate) to determine the asymptotics of the Shannon function for their complexity.     

Complexity of functions from some classes of three-valued logic

The problem of the realization complexity for functions of the three-valued logic taking values from the set {0, 1} by formulas over incomplete generating systems is considered. Upper and lower asymptotic estimates for the corresponding Shannon functions are obtained.     

Behavior of the shannon function for some families of classes of three-valued logic functions

A certain countable set of families of classes of three-valued logic functions taking values from the set {0,1} is considered. For each class from these families and for each its finite generating system, the order of growth of the corresponding Shannon depth function is obtained.     

Depth of <Emphasis Type="Italic">α</Emphasis>-completions of systems of Boolean functions

A problem of realization of Boolean functions by α-formulas is considered. These formulas are such that each subformula contains not more than one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for α-completions of finite systems of Boolean functions are obtained.     

Synthesis of formulas whose complexity and depth do not exceed the asymptotically best estimates of high degree of accuracy

We study problems concerning optimal realizations of arbitrary Boolean functions by formulas in the standard basis {&;, V, ¬} in the presence of two optimality criteria: the depth and the complexity. Both the complexity and depth of Boolean functions are investigated from the point of view of so-called asymptotically best estimates of high degree of accuracy for the corresponding Shannon functions. Such estimates produce an asymptotics not only for the Shannon function, but also for the first remainder term of its standard asymptotic expansion. For any Boolean function depending on n variables, we prove that it is possible to construct a realizing formula in the basis {&;, V, ¬} so that its depth and complexity do not exceed values of the corresponding Shannon functions for the argument equal to n in the sense of asymptotic estimates of high degree of accuracy.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3

The realization complexity of Boolean functions associated with finite grammars in the class of formulas of alternation depth 3 is studied. High accuracy asymptotic bounds are obtained for the corresponding Shannon function.     

On the strong CE-property of convex sets

We consider a class of convex bounded subsets of a separable Banach space. This class includes all convex compact sets as well as some noncompact sets important in applications. For sets in this class, we obtain a simple criterion for the strong CE-property, i.e., the property that the convex closure of any continuous bounded function is a continuous bounded function. Some results are obtained concerning the extension of functions defined at the extreme points of a set in this class to convex or concave functions defined on the entire set with preservation of closedness and continuity. Some applications of the results in quantum information theory are considered.     

Estimate of the concentration function for a class of additive functions

We show how methods for estimating the concentration function of the sum of independent random variables can be used to obtain estimates of the concentration function for the values of additive functions under suitable conditions. Previously obtained estimates of the concentration function are consequences of the estimate obtained in the present paper for functions from of the class under consideration.     

Estimates of reachable sets of multidimensional control systems with nonlinear interconnections

The paper is devoted to the problem of constructing external estimates for the reachable set of a multidimensional control system by means of vector estimators. A system is considered that permits a decomposition into several independent subsystems with simple structure (for example, linear subsystems), which are connected to each other by means of nonlinear interconnections. For each of the subsystems, an external estimate of the reachable set is assumed to be known; this estimate is representable in the form of a level set of some function satisfying a differential inequality. An estimate for the reachable set of the combined system is constructed with the use of estimates for subsystems. The method of deriving the estimates is based on constructing comparison systems for analogs of vector Lyapunov functions (value functions).     

Regularizing algorithms for localization of breakpoints of noisy functions

The problem of localizing the singularities (breakpoints) of functions that are noisy in the spaces L _p , 1 < p < ∞, or C is considered. A wide class of smoothing algorithms that determine the number and location of breakpoints is constructed. In addition, for the case when a function is noisy in C, a finite-difference method is constructed. For the proposed methods, convergence theorems are proved and approximation accuracy estimates for the location of breakpoints are obtained. The lower estimates obtained in this paper show the order-optimality of the methods. For all the methods constructed, their capacity of separating close breakpoints is investigated.     

Asymptotic behavior of Shannon functions for the delays of schemes of functional elements

The behavior of Shannon functions for delays in the class of schemes of functional elements constructed over an arbitrary finite complete basis is studied. The case in which every basis element can have positive as well as zero delay is considered in this note. It is established that in this case the Shannon functions for delays asymptotically behave either as linear functions or as logarithmic functions or, starting from a certain number of arguments, remain constant.Translated from Matematicheskie Zametki, Vol. 19, No. 6, pp. 939–951, June, 1976.In conclusion the author thanks O. B. Lupanov for guidance during the preparation of this note.     

Complexity of Boolean functions in the class of polarized polynomial forms

It is proved that values of Shannon functions in the class of polarized polynomial forms (generalized Reed-Muller forms) coincide for classes of all Boolean functions and all symmetric Boolean functions; a formula computing estimates for these functions is derived. Translated fromAlgebra i Logika, Vol. 34, No. 3, pp. 323-326, May-June, 1995.     

Cubic spline interpolation of functions with high gradients in boundary layers

The cubic spline interpolation of grid functions with high-gradient regions is considered. Uniform meshes are proved to be inefficient for this purpose. In the case of widely applied piecewise uniform Shishkin meshes, asymptotically sharp two-sided error estimates are obtained in the class of functions with an exponential boundary layer. It is proved that the error estimates of traditional spline interpolation are not uniform with respect to a small parameter, and the error can increase indefinitely as the small parameter tends to zero, while the number of nodes N is fixed. A modified cubic interpolation spline is proposed, for which O((ln N/N)⁴) error estimates that are uniform with respect to the small parameter are obtained.     

On the Parameter-Uniform Convergence of Exponential Spline Interpolation in the Presence of a Boundary Layer

The paper is concerned with the problem of generalized spline interpolation of functions having large-gradient regions. Splines of the class C², represented on each interval of the grid by the sum of a second-degree polynomial and a boundary layer function, are considered. The existence and uniqueness of the interpolation L-spline are proven, and asymptotically exact two-sided error estimates for the class of functions with an exponential boundary layer are obtained. It is established that the cubic and parabolic interpolation splines are limiting for the solution of the given problem. The results of numerical experiments are presented.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

On mean integral values of solutions of the generalized Cauchy-Riemann equations

Formulas of the Cauchy and Poisson types for polyanalytic functions are obtained in this work. On the basis of these formulas, the mean-value theorem and the generalized maximum principle are obtained for polyanalytic functions. Estimates for mean values of the associated function of two complex variables on the circles expressed through the mean values of the polyanalytic function itself are obtained. In particular, this implies the estimates for integral norms of analytic components of the polyanalytic function considered. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 36, Suzdal Conference-2004, Part 2, 2005.     

On the Size of the Exceptional Set in Nevanlinna's Second Fundamental Theorem for Certain Classes of Meromorphic Functions

Some conditions on the size of the exceptional set that arise in Nevanlinna's Second Fundamental Theorem are established, showing that previous sharp results can be improved by restricting the class of functions considered and suggesting a close relationship between the size of the exceptional set and the lower growth of the characteristic function. Examples of functions of rapid growth possessing exceptional sets are built, showing that these conditions are sharp for the class of functions considered.     

Network delay in a model with inputs of functional elements

We consider a model of delays in networks of functional elements in an arbitrary finite complete basis B, where the delays of basis elements are arbitrary positive real numbers for each input and each input set of variables going to the remaining inputs. This model estimates the delays in a multiplexer function of nth order asymptotically as τ_B n ± O(logn), where τ_B is a constant depending only on the basis B. On the basis of these estimates and within this model, asymptotic estimates of the form τ_B n ± O(logn) are obtained for the corresponding Shannon function, i.e., for the delay of the “worst” Boolean algebra function of given n variables.     

On small circles containing zeros and ones of analytic functions

Gol'dberg considered the class of functions with unequal positive numbers of zeros and ones inside the unit disc. The maximum modulus of zeros and ones in this class is bounded from below by a universal constant. This constant determines the limits of certain controller designs as well as covering regions of certain composites with schlicht functions. Considering lower bounds in a zero-free region of the extremal function the best known estimates of this constant are improved.