О нижних оценках сложности схем в базисе антицепных функций
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem find their applications in different applied areas among each are problems of integral circuits design. Traditional synthesis problem under study particularly concerns the study of the Shannon function for delay, i.e. the delay of the “worst” Boolean function that depends on a given set of n variables. A number of classic results in the theory of discrete control systems concerned with construction of circuits that are asymptotically optimal according to several parameters simultaneously apply to the described problem.
The goal of the work is to carry known results in the area of circuit synthesis, that apply to simultaneous circuits optimization over several parameters, over circuit models that reflect capacitive peculiarity of gate interconnections with greater accuracy and also reflect timing parameters of gates under different input signals. The work considers a delay model over an arbitrary finite complete basis where delay of the gate (a positive real quantity) over any of its inputs depend on signals passed on its other inputs and is composed of two components: the gates interconnection delay of the input with the output of the previous gate, and the inner delay of the gate. Meanwhile, delays of a gate over its different inputs are, generally speaking, considered to be independent values.
Materials and methods
Used instruments involve the technique of universal sets of Boolean functions and technique of Boolean functions modelling on components of Boolean cube special partitions. The synthesis method of formula type circuits that are asymptotically optimal both by complexity and by delay is implemented for circuit synthesis in the described delay model.
Obtained linear in regard to n Shannon function asymptotic for the delay of Boolean functions that depend on a given n variables. It is proved that incorporation of an additional delay component such as its input signals dependence doesn’t lead to a change of Shannon function asymptotical behavior. Formula type circuits asymptotically optimal both by complexity and by delay are constructed.
Established results allow to educe the applicability of the earlier known results concerned with simultaneous formula type circuits optimization over several parameters to a wider class of delay models.
Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The non-monotone part of the basis consist of the only negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function f equal ]log2(d(f)+1)[. Here d(f) is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples.mThe aim of this paper is to prove that the complexity of a boolean function f realization equal ρ]log2(d(f)+1)[-O(1), where ρ is the minimum weight of non-monotone basis elements. Similar generalization of classical Markov result concerning realization of boolean funciton systems was obtained.
The paper puts forward a nontrivial lower estimate 13n/6 or the cardinality of the domain of a universal function for the class of linear Boolean functions, where n is the number of variables.for the cardinality of the domain of a universal function for the class of linear Boolean functions, where n is the number of variables.
Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.
Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.