О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами
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 problem of multi-valued functions realization by circuits over special basis is inverstigated. The basis consis of Post negation and all monotone functions.
The complexity of realization of k-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (d(f)+1)+O(1), here d(f) is the maximum number of the value decrease of the value of f taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.
The paper is devoted to testing critical Software Defined Networking (SDN) components and in particular, SDN-enabled switches. A switch can be seen as a forwarding device with a set of configured rules and thus, can be modelled and analyzed as a ‘stateless’ system. Correspondingly, in this paper we propose to use appropriate logic circuits or networks to model the switch behavior. Both active and passive testing modes can benefit from such representation. First, this allows applying well-known test generation strategies such as for example, test derivation techniques targeting Single Stuck-at Faults (SSFs). We also specify a number of mutation operators for switch rules and propose an algorithm for eliminating equivalent mutants via SAT solving. Logic circuits simulating the behavior of the switches can be effectively utilized for run-time verification, and such logic circuit based approach is also discussed in the paper. Preliminary experimental results with Open vSwitch, on one hand, demonstrate the necessity of considering new fault models for logic circuits (apart from, for example well established SSFs) and on the other hand, confirm the efficiency of the proposed test generation and verification techniques.
The book presents the basic concepts of the theory of transition circuitry required for the development of a new element base of different types of supercomputers. The theory of transition circuitry differentiates the new concept of synthesis of nanostructures, in which the minimum component in the synthesis is not a transistor, but the material and the transition (connection) between the materials. The data of experimental 2D and 3D modeling of the physical and electrical processes in silicon transitional nanostructures with a minimum design rule of 10-20 nm and a comparative analysis of the four types of circuitry are presented.
In the first volume, logical schemes of computers are considered.
Models, schemes and nanostructures of logical elements and schemes of a bionic computer are presented.
In 1992, A. Hiltgen provided first constructions of provably (slightly) secure cryptographic primitives, namely feebly one-way functions. These functions are provably harder to invert than to compute, but the complexity (viewed as the circuit complexity over circuits with arbitrary binary gates) is amplified only by a constant factor (in Hiltgen’s works, the factor approaches 2). In traditional cryptography, one-way functions are the basic primitive of private-key schemes, while public-key schemes are constructed using trapdoor functions. We continue Hiltgen’s work by providing examples of feebly secure trapdoor functions where the adversary is guaranteed to spend more time than honest participants (also by a constant factor). We give both a (simpler) linear and a (better) non-linear construction.
A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.