2018 year, volume 22, issue 1 (PDF)

Agafonova M. V. On a class of neural functions with binary-rational parameters

The paper deals with a class of neural piecewise-parallel functions with binary-rational coefficients. It is proved that for any function in the class of piecewise-parallel functions there exists a function in the class of piecewise-parallel functions with binary-rational coefficients that approximates it with a predetermined accuracy. Also, for the class of functions under consideration, it is shown that there exist bases consisting of arbitrary number of elements, in particular, a Scheffer function is found.

Keywords: class of piecewise-parallel functions, class of neural functions with binary-rational coefficients, superposition operations, Scheffer function, bases.

Piven N.A. Investigations of quasigroups generated by proper families of boolean functions of order 2

We analyze all Latin squares of order 4 generated by proper families of Boolean functions. It turns out that all these Latin squares define polynomially incomplete quasigroups. We propose a generalization of the construction based on proper families. As a result, the number of generated Latin squares grows four times, and an essential number of the corresponding quasigroups becomes polynomially complete.

Keywords: Quasigroup, Latin square, parametric assignment, polynomial completeness, proper families of functions

Ivanov I.E. About automaton functions for pushdown automaton

Realtime pushdown transducer saves the set of periodic sequences. Earlier the author found upper and lower bounds for max period of output for transducer without input as a function from parameters of transducer. There are upper and lower bounds for max period of output in general case in current paper. The max period of transducer output has been studied as function from period of input sequence.

Keywords: realtime pushdown transducer, deterministic function, periodic sequences.

Kalachev G. V. On the lower bound for the maximum potential of plain circuits with several outputs through the area

In this paper we consider the relationship between the area and the maximum potential of plain circuits realizing Boolean operators. The maximal potential is a complexity measure of plain circuits, reflecting the power consumption of the circuit in the worst case, it is also often called activity. It is equal to the maximum number of outputs of circuit elements equal to 1, where the maximum is taken over all input sets of the circuit. It was porved that for arbitrary Boolean operator f, its maximal potential \(\hat{U}\) is greater or equal than \(\sqrt{S} /4 \sqrt{2} \) where S is the area of the minimal plain circuit realizing f .

Keywords: plain circuits, activity, potential, retations between complexity measures, lower bounds, Boolean operators.

Bokov G. V. From Boolean circuits to theorem proving

The question how difficult it is to prove given theorems in given formal systems arises in many areas. In computational complexity, lower bounds to the size of proofs offer an approach towards the separation of complexity classes. Analysis of proof systems underlying recent SAT solvers provides the main theoretical framework towards understanding the power and limitations of solving. The main part of research in proof complexity has concentrated on proof systems for classical propositional logic. Despite the fact that propositional proof complexity has made enormous progress over the past three decades in showing tight lower and upper bounds for many proof systems, some of strong classical proof systems have resisted all attempts for lower bounds for decades. Nevertheless, a general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. In the paper we show how relates Boolean circuits and proof systems with respect to complexity, i.e. how ideas and techniques from Boolean circuit complexity applies to propositional proof complexity.

Keywords: Propositional proof systems, proof complexity, Boolean circuits, circuit complexity, complexity classes.

Zhuk D.N. From two-valued logic to k-valued logic.

Traditionally, it is believed that the lattices of clones in two-valued logic and k-valued logic are totally different. In the paper we show that despite the differences they have a lot in common, and many properties that follow from the Post lattice can be generalized to the multi- valued case. As an example we show that the most general polynomial algorithm for the constraint satisfaction problem on k-element set can be viewed as a combination of methods known for two-valued case.

Keywords: Boolean functions, k-valued functions, relations, Galois connection, constraint satisfaction problem.

Panteleev P.A. A generalization of a Moore theorem

Distinguishing sequences for finite automata were first introduced in the classical paper of E. Moore and since that they have many applications in testing of sequential circuits and communication protocols. One of the basic tasks in the testing of finite automata is to identify the initial state of the automaton under investigation. Suppose we have a full description of a finite deterministic Mealy automaton and we know that its initial state is in some subset of its set of states. Then the state-identification problem is to find the initial state by a sequential application of input symbols to the automaton. In this talk we discuss the bounds on the length of such input sequences and show a relation of this problem to combinatorial problems in hypergraph theory.

Keywords: Finite automaton, adaptive distinguishing sequence, Moore theorem, hypergraph.

← Back to archive