Search

The behaviour of automata in lybrinths is a rather new field of automata theory, but more than one hundred papers devoted to this topic have been published. In this paper, we consider the key notions, problems, achievements, methods to solve problems related to an important direction of this field, the behaviour of collectives of automata in labyrinths. In a series of cases, we give base assertions in a more strong form and give a more general presentation that the authors of the corresponding papers do. New results are also contained in this survey. [ABSTRACT FROM AUTHOR]

This paper is a continuation of the paper 'Functions without short implicents. Part I: lower estimates of weights'. In Part II we propose various methods of construction of n-place Boolean functions not admitting implicents of k variables. The first of the methods proposed is based on the gradient algorithm, the second and the third ones depend on a certain combinatorial principle of construction, while the fourth method is based on a random choice of elements in the function support. The above methods have different efficiency depending on the value of k. We give upper estimates for the minimal value w ( n, k) of weights of the so-constructed functions. Together with the lower estimates of w ( n, k) from the first part of the paper this allows us to obtain an asymptotically sharp estimate w ( n, k) = Θ (ln n) as n → ∞. [ABSTRACT FROM AUTHOR]

The paper is concerned with representations of predicates over a finite set in the form of generalized conjunctive normal forms (GCNF). Properties of predicates GCNF are found which are preserved by some majority function. Such predicates are called generalized bijunctive predicates. These properties are used to construct new faster polynomial algorithms for the generalized satisfiability problem in the case when some majority function preserves all the original predicates. [ABSTRACT FROM AUTHOR]

We study the lattices ΩKn and Kn of all n-multiply Ω-canonical and n-multiply canonical formations respectively. The main results of the paper are the proofs of G-separability of the lattice ΩKn and coincidence of the systems of identities of the lattices Kn and Km for different positive integers n and m. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the lattice of all Fitting classes, the lattice of all n-multiply Ω-foliated Fitting classes with direction ϕ, ψ0 ≤ ϕ, and the lattice of all totally canonical Fitting classes. It is shown that these lattices are algebraic with l-generated compact elements. [ABSTRACT FROM AUTHOR]

The paper gives lower bounds for the minimum number m of weighings that are necessary for identification of up to t non-standard objects out of the total number of n objects being tested. For the problem with fixed deviation of weights of non-standard objects we construct a perfect algorithms with parameters n = 11, m = 5, t = 2 corresponding to the parameters of the ternary Virtakallio-Golay code. The nonexistence of a perfect weighing code with such parameters is proved. [ABSTRACT FROM AUTHOR]

The notion of p-language was introduced by the author. A p-language is the set of words that appear at the output of some automaton at least p times. Previously it was shown that any p-language is regular; however it was unclear whether it is decidable that a regular language is a p-language. The paper is devoted to the solution of this problem. [ABSTRACT FROM AUTHOR]

In this paper we suggest a combined method for solving systems of Boolean polynomial equations based on testing a part of variables and using monomial compatibility criteria for dropping out some values of the tested variables. The complexity of the method is estimated for various parameters of the system. [ABSTRACT FROM AUTHOR]

In this paper we study the average complexity of optimal algorithms solving the problem of searching for identical objects (PSIO) for random databases. We describe and investigate classes of PSIOs for which the average complexity as a function of the database volume grows logarithmically. For such classes of problems we find exact asymptotics of the complexity. We also study the case where the complexity of the optimal algorithm averaged over the class of problems is bounded and construct a class of PSIOs such that the average complexity of the optimal algorithm is an unbounded function growing slower than the logarithm. [ABSTRACT FROM AUTHOR]

We consider efficient algorithms of calculation of the characteristic polynomials of matrices over commutative rings. We give estimates of complexity treated as the number of ring operations, and for the ring of integers the estimates are presented in terms of the number of multiplication operations over the machine words. We suggest a new algorithm to calculate the characteristic polynomial which has the best estimate of complexity in the ring operations. We give recommendations concerning applications of the algorithm of calculation of the characteristic polynomials depending on the size of the matrix, in particular, the algorithm suggested in this paper is recommended to be applied to integer-element matrices of size greater than 60. [ABSTRACT FROM AUTHOR]

Let u be a linear recurring sequence of maximal period over the ring Z pn and 𝑣 be a pseudo-random sequence over the field Z p obtained by multiplying the highest coordinate sequence of u by some polynomial. In this paper we analyse possibilities and ways to restore u from a given 𝑣. A short survey of earlier results is given. [ABSTRACT FROM AUTHOR]

One of the key results of the theory of matroids is the well-known Rado–Edmonds theorem which states that the problem of maximising an additive function on an independence system is solvable by the greedy algorithm if and only if the independence system is a matroid. Many generalisations of the Rado–Edmonds theorem were related in main with extension of the set of feasible solutions of the maximisation problem, as a rule an independence system was replaced by an accessible set system. Extension of the class of objective functions was also accompanied by extension of the feasible sets. In this paper, we investigate the maximisation problems of nonadditive functions of sets on independence systems. We suggest a characterisation of the class of objective functions of the problems on matroids which are solvable by the greedy algorithm. We proved a generalisation of the Rado–Edmonds theorem for the maximisation problem on the independence system of a nonadditive function of a given class. [ABSTRACT FROM AUTHOR]

Proofs of security for practical signature schemes are known in idealised models only. In the present paper, we consider the tamper-proof device model that does not use ideal primitives. Instead of access to a random oracle each participant is provided with tamper-proof device implementing a private-key cryptosystem. The hash-value of a message to be signed is submitted to the tamper-proof device for encryption and this encrypted value is used in the signature generation algorithm. In this model, we prove, modulo a physical assumption, a necessary and sufficient condition for security of the GOST signature scheme. [ABSTRACT FROM AUTHOR]

In this paper we suggest a new algorithm of anti-unification of logic terms represented by acyclic directed graphs and estimate its complexity. The anti-unification problem consists of the following: for two given terms find the most specific term that has the given terms as instances. We suggest an anti-unification algorithm whose complexity linearly depends on the size of the most specific term it computes. It is thus established that the anti-unification problem is of almost the same complexity as the unification problem. It is also shown that there exist terms whose most specific term is of size O( n2), where n is the size of the graphs representing these terms. [ABSTRACT FROM AUTHOR]

A Boolean function g is said to be an annihilator of a Boolean function f if fg = 0. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function f. In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function f, yields a basis of the space of its annihilators of degree not exceeding d. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases. The research was supported by the Russian Foundation for Basic Research, grants 05–01–00798 and 04–01–00359. [ABSTRACT FROM AUTHOR]

On the set of all infinite binary sequences, we consider the simplest form of algorithmic reducibility, namely, the Boolean reducibility. Each set Q of Boolean functions which contains a selector function and is closed with respect to the superposition operation of special kind generates the Q-reducibility and Q-degrees, the sets of Q-equivalent sequences. The Q-degree of a sequence α characterises the relative 'informational complexity' of the sequence α, in a sense, Q is a set of operators of information retrieval from infinite sequences. In this paper, we study the partially ordered sets ℒQ of all Q-degrees for the most important classes Q of Boolean functions. We investigate the positions of periodic and narrow Q-degrees in ℒQ, find the number of minimal elements and atoms and also the initial segments isomorphic to given finite lattices. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783. [ABSTRACT FROM AUTHOR]

The distribution of jobs in a system with m identical parallel processors which minimises the load of the maximally loaded processor is an NP-hard problem. Many approximate algorithms are developed for this problem, but for the version of the problem where the jobs arrive ad must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than 1 + 1 / ... for m ≥ 4 and tends to 1.837 as m → ∞. In this paper, we consider the version of the problem where jobs arrive one by one and must be treated on-line under the additional condition that the total duration of the jobs is known. For this version of the problem we suggest an algorithm with the guaranteed estimate equal to 5/3. [ABSTRACT FROM AUTHOR]

In this paper we study the maximally non-Hamiltonian graphs (MNH graphs), that is, the graphs whose property to be non-Hamiltonian ceases to exist as soon as an edge is added. We give rules how to construct MNH graphs which make it possible, starting from MNH graphs with some properties, to get MNH graphs of greater order. [ABSTRACT FROM AUTHOR]

We consider polynomials f(x1, ..., xn) over a finite field that possess the following property: for some element b of the field the set of solutions of the equation f(x1, ..., xn) = b coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with respect to the right-hand side b. We obtain the properties of multiaffine polynomials over a finite field. Then we show that checking the multiaffinity with respect to a given right-hand side may be done by an algorithm with polynomial (in terms of the number of variables and summands of the input polynomial) complexity. Besides that, we prove that in case of the positive decision a corresponding system of linear equations may be recovered with complexity which is also polynomial in terms of the same parameters. [ABSTRACT FROM AUTHOR]

We introduce a new model P-CNAR(s) of sequences of discrete random variables with long memory determined by semibinomial conditionally nonlinear autoregression of order s ∈ ℕ with small number of parameters. Probabilistic properties of this model are studied. For parameters of the model P-CNAR a family of consistent asymptotically normal statistical FB-estimates is suggested and the existence of an efficient FB-estimate is proved. Computational advantages of FB-estimate w.r.t. maximum likelihood estimate are shown: less restrictive sufficient conditions for uniqueness, explicit form of FB-estimate, fast recursive computation algorithm under extension of the model P-CNAR. Subfamily of "sparse" FB-estimates that use some subset of frequencies of s-tuples is constructed, the asymptotic variance minimization problem within this subfamily is solved. [ABSTRACT FROM AUTHOR]

We investigate the possibility to use non-associative groupoids in the realization of an open key distribution procedure based on a generalization of the well known Diffie-Hellman algorithm.We prove the existence of non-associative groupoidswhich are simultaneously power commuting and not power-associative. [ABSTRACT FROM AUTHOR]

The hash algorithms of the MDx family involve cyclic shifts, computation of primitive Boolean functions, and addition of constants. So far, very few works have been published in which the authors attempt to explain the impact that the choice of constants, shifts, and Boolean functions has on the cryptographic properties of the algorithms. G. A. Karpunin and H. T. Nguyen suggested a model in which the resistance against differential cryptanalysis may be quantitatively estimated in terms of the number of solutions of a special equation. In this work, in the framework of the aforementioned model, an equation for the MD5 hash function is derived. Examination of one Boolean function and one value of the cyclic shift through exhaustive search requires 2128 operations of computation of the step of the hash function. The formulas suggested in the present work allow to reduce the complexity of the examination to 244 arithmetic operations. [ABSTRACT FROM AUTHOR]

The algorithmic complexity of periodicity detection of Boolean functions given in a polynomial form is investigated. A function is said to be periodic with period ó if it takes the same values on input strings which differ only by inverting the components corresponding to nonzero entries in the bit string ó. Two polynomial-time algorithms for checking whether a given bit string is a period of a given Boolean function are presented. The relationship between the periods of a function and the length of its polynomial is investigated. The problem of finding the periods is explicitly reduced in polynomial time to the problem of solving a system of Boolean equations. [ABSTRACT FROM AUTHOR]

The notion of cycle indices of an automaton is introduced as a pair of positive parameters (b, q) effectively evaluated by the automaton. It is shown that the totality of periods of constant automata which may be represented as superpositions of a given automaton, Boolean functions, and the delay element, coincides with the variety of divisors of the members of the geometric progression b, bq, bq2,... This suggests an algorithm for checking the expressibility of constant automata, as well as a theorem on the verification of the expressibility of the totality of all automata with a limited number of states. [ABSTRACT FROM AUTHOR]

It is well known that the problem on A-completeness of finite systems of b.d. functions is algorithmically unsolvable in the general case. Nevertheless, the criterion for A-completeness admits a formulation in terms of A-precomplete classes, and the set of A-precomplete classes is described efficiently. We consider systems of b.d. functions containing all S-b.d. functions depending on one variable and demonstrate that there exists an algorithm to recognise the A-completeness of such systems. [ABSTRACT FROM AUTHOR]

We introduce the notion of steepness of a coordinate-convex function of discrete argument on an ordinal-convex set. In terms of guaranteed estimates it is shown that in problems of optimisation of coordinate-convex functions on an ordinal-convex set the gradient coordinatewise lifting algorithm is stable under small perturbations of the utility function. As corollaries we obtain improved guaranteed estimates for accuracy of the gradient algorithm, and also new sufficient conditions for the values of the utility function of the problem under consideration to coincide in the global and gradient extrema. [ABSTRACT FROM AUTHOR]

In the context of the approach given in Shannon's research [[Bell Syst. Tech. J. 28: 656--715, 1949]], of interest are the mixing properties of operations in a finite field, in particular, the action of each operation on cosets with respect to the action of the second operation. The good mixing properties give a possibility to construct on this base good cryptographic algorithms. [ABSTRACT FROM AUTHOR]

In the algebra of linear integer-coefficient polynomials, we give a criterion of completeness in terms of precomplete classes and find the cardinality of bases. [ABSTRACT FROM AUTHOR]

We obtain two-sided bounds and asymptotic formulas for the number of Boolean functions of n variables which are approximated by affine or linear Boolean functions with a given accuracy. [ABSTRACT FROM AUTHOR]

The objective of this research is to study the complexity of multiplication in commutative group algebras over arbitrary fields of prime characteristic. In order to solve this problem, we suggest a method to find the structure of group algebras which allows us to use the Alder-Strassen theorem to obtain lower bounds and the Bläser theorem describing all algebras of minimal rank to obtain upper bounds. [ABSTRACT FROM AUTHOR]

We suggest an algorithm calculating the limit probabilities of the distribution of the permanent of a random matrix Amn = | αij| with m rows and n independent columns over the field GF( p). [ABSTRACT FROM AUTHOR]

We consider systems of the form M = F ∪ ν, where F is some Post class and ν is a finite system of definite automata. We divide the Post classes into those for which the problem of A-completeness of such systems of definite automata is algorithmically decidable and those for which the problem of A-completeness is algorithmically undecidable. [ABSTRACT FROM AUTHOR]

It is shown that the inversion of a complex-valued power series can be realised asymptotically with complexity of 5/4 multiplications (if we compare the upper bounds). It is shown that the calculation of the square root requires asymptotically also no more than 5/4 multiplications, the computation of an exponential has the complexity equal to 13/6 multiplications, and raising to an arbitrary power requires 41/12 multiplications. [ABSTRACT FROM AUTHOR]

Let c ≥ 2 and p ≥ c be two integers. We say that a proper colouring of the graph G is ( c, p)-nondegenerate, if for any vertex of G of degree at least p there are at least c vertices of different colours adjacent to it. In this research we prove the following result which generalises the Brooks theorem. Let D ≥ 3 and G be a graph without cliques on D + 1 vertices and a degree of any vertex in this graph be no greater than D. Then for any integer c ≥ 2 there is a proper ( c, p)-nondegenerate vertex D-colouring of G, where p = ( c3 + 8 c2 + 19 c + 6)( c – 1). [ABSTRACT FROM AUTHOR]

For Coxeter groups of extra large type, the power conjugacy problem for words and the problem of intersection of cyclic groups are solved; for the second problem we suggest an algorithm which for two elements finds the generator of the intersection of their cyclic subgroups. [ABSTRACT FROM AUTHOR]

We investigate the complexity of basic operations over dynamic databases including search, insertion, and deletion of records. We suggest a structure of a database and corresponding algorithms which with the use of two parallel computing processes permit to fulfil these operations over a database in a constant time on the average and with logarithmic complexity in the worst case. [ABSTRACT FROM AUTHOR]

We suggest an algorithm to test numbers of the form for primality, where , k is an odd positive integer, is a prime number, i = 1,..., n, and . The algorithm makes use of the Lucas functions. The algorithm suggested is of complexity Ô(log2 N). [ABSTRACT FROM AUTHOR]

We construct a combinatorial representation of an octahedral polyhedron (crystal), find its geometrical parameters, and show that the parameters of such a polyhedron and its mirror image coincide and are simply measured. Using the combinatorial representation of a diamond, we are able to construct an algorithm which finds a round cut diamond of maximum radius embedded into an octahedral diamond and determines how to place this cut diamond in the octahedral one. This results in creating a technological process to cut round diamonds of maximum value from octahedral ones. [ABSTRACT FROM AUTHOR]

A system of generators of a group consisting of three involutions, two of which commute, is called a Mazurov triple. We describe algorithms for finding in an explicit form the Mazurov triples of one of the sporadic Monsters, the finite simple group B, and for constructing a Hamiltonian cycle in the Cayley graph of the finite group with Mazurov triple. We give examples of Hamiltonian cycles in the Cayley graphs of some groups. [ABSTRACT FROM AUTHOR]

We suggest a new block algorithm for solving sparse systems of linear equations over GF(2) of the form where A is a symmetric matrix, F = GF(2) is a field with two elements. The algorithm is constructed with the use of matrix Padé approximations. The running time of the algorithm with the use of parallel calculations is max{ O( dN2/ n), O( N2)}, where d is the maximal number of nonzero elements over all rows of the matrix A. If d < Cn for some absolute constant C, then this estimate is better than the estimate of the running time of the well-known Montgomery algorithm. [ABSTRACT FROM AUTHOR]

It is proved that in any commutative semigroup the complexity of transformation of equal terms of length at most n into each other is of order n log n. [ABSTRACT FROM AUTHOR]

The problem of packing rectangles into several strips is considered. It is shown that for this problem there exist on-line algorithms with multiplicative error asymptotically close to 2 e, where e is the base of the natural logarithm. It is proved that none of the on-line algorithms can have the asymptotic multiplicative error less than e. [ABSTRACT FROM AUTHOR]

We present an algorithm producing a dynamic non-self-financing hedging strategy in an incomplete market corresponding to investor-relevant risk criterion. The optimisation is a two stage process that first determines admissible model parameters that correspond to the market price of the option being hedged. The second stage applies various merit functions to bootstrapped samples of model residuals to choose an optimal set of model parameters from the admissible set. Results are presented for options traded on the New York Stock Exchange. [ABSTRACT FROM AUTHOR]

The algebraic method is widely used in analysis of filter generators of pseudo-random sequences. It is based on obtaining low-degree Boolean equations in bits of the initial states of the generator. The problem to obtain such equations reduces to finding low-degree annihilators for the filtering Boolean function. The presence of nonzero low-degree annihilators decreases the complexity of determining the initial state of the generator by means of its output. In this research we deal with the problem to find all low-degree annihilators for a Boolean function defined as a polynomial in several variables. We propose two new algorithms which solve this problem. Their complexities are bounded above by polynomials of the number of variables of the function and of the number of monomials in the polynomial which defines the function. We also consider the application of these algorithms to realising the algebraic method by three known scenarios which yield low-degree equations. [ABSTRACT FROM AUTHOR]

We give an example of a quasi-universal function in the class ε2 of the Grzegorczyk hierarchy. This function is of very simple structure and does not contain an explicit enumeration of any Turing machine. As a corollary we obtain a simple basis over superposition in the class ε2. [ABSTRACT FROM AUTHOR]

We suggest an algorithm to test numbers of the form N = 2kpm - 1 for primality, where 2k < pm, k is an odd positive integer, 2k < pm, p is a prime number, and p = 3 (mod 4). The algorithm makes use of the Lucas functions. First we present an algorithm to test numbers of the form N = 2k3m - 1. Then the same technique is used in the more general case where N = 2kpm - 1. The algorithms suggested here are of complexity O((log N)2 log log N log log log N). [ABSTRACT FROM AUTHOR]

We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable. The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. [ABSTRACT FROM AUTHOR]