Computer Sciences

Automata on algebraic structures

Authors: Skobelev V. V.

A survey of results obtained in investigations of automata determined over finite algebraic structures. The objects of research are automata over some finite ring, automata determined in terms of ideals, automata over varieties, and families of hash-functions determined by automata without output function. Computational security, complexity of simulation and homomorphisms of investigated automata are characterized. 

Combining de Bruijn graphs, overlap graphs and microassembly for de novo genome assembly

Authors: Sergushichev A. A., Aleksandrov A. V., Kazakov S. V., Tsarev F. N., Shalyto A. A.

 In this paper we present a method for de novo genome assembly that splits the process into three stages: quasicontig assembly; contig assembly from quasicontigs; contig postprocessing with microassembly. The first stage uses de Bruijn graph, the second one uses overlap graph. We have carried out experiments of assembling the E. Coli genome (size ≈4.5 Mbp) andMaylandia zebra genome (size ≈1 Gbp). Advantage of proposed method is a low memory consumption. 

The ordered set of connected parts of a polygonal graph

Authors: Salii V. N.

Under a polygonal graph is meant an oriented graph obtained from a cycle by some orientation of its edges. The set of all abstract (i.e. pairwise non-isomorphic) connected parts of a polygonal graph is ordered by graph embedding. Polygonal graphs are characterized for which this ordered set is a lattice. 

Models of multi-criteria optimization with quality criteria

Authors: Rozen V. V., Smirnova D. S.

We consider mathematical models of multi-criteria optimization with quality criteria. The main problem is a construction of preference relations on the set of alternatives and an investigation of its mathematical properties. Two methods for contraction of Pareto-optimal set are proposed. The first method is based on introduction of a partial order relation on the set of criteria and the second leans selection of the most important groups of criteria. 

Representation of universal planar automata by autonomous input signals

Authors: Molchanov V. A.

Universal planar automata are universally attracted objects in the category of automata, whose sets of states and output signals are endowed with structures of planes. The main result of the paper shows that any universal planar automaton is isomorphic to a many-sorted algebraic system canonically constructed from autonomous input signals of the automaton. 

Queueing networks with batch movements of customers, blocking and clusters

Authors: Mitrophanov Y. I., Dolgov V. I., Rogachko E. S., Stankevich E. P.

 Two types queueing networks with batch movements of customers – networks with blocking and networks with clusters are investigated. Product form stationary distribution for networks with blocking of transitions in states, in which the number of customers in queueing systems exceeds given values, is derived. For queueing networks with disjoint clusters of systems the problem of analyzing is solved and the product form stationary distribution is found. Examples of analysis of the network with blocking and the network with clusters are presented. 

Identification of a state machine structure with finites fragment of behavior

Authors: Bogomolov S. A.

 Identification of a state machine structure with finite fragments of behavior is discussed. The state machine behavior is a set of various finite-sequential (f.-s.) functions realized in a state machine, and under a finite fragment of behavior we mean traces of f.-s. functions and state machines. The concept of an identifying trace for a state machine irredundant over its realization is introduced.

On stability theory of autonomous angular stabilization system for combined dynamical systems

Authors: Andreichenko D. K., Andreichenko K. P., Kononov V. V.

Studied the effect on the stability of the longitudinal acceleration discretely-continuum model of single-channel angular stabilization system with of delayed argument. Methods of construction asymptotic stability areas and analysis of impulse transition functions are developed. The critical values of the longitudinal acceleration are defined. 

Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension

Authors: Abrosimov M. B.

A graph G∗ is a k-vertex extension of a graph G if every graph obtained from G∗ by removing any k vertices contains G. k-vertex extension of a graph G with n+k vertices is called minimal if among all k-vertex extensions of G withn+k vertices it has the minimal possible number of arcs. We study directed graphs, whose minimal vertex 1-extensions have a specific number of additional arcs. A solution is given when the number of additional arcs equals one or two. 

Analysis of closed unreliable queueing networks with batch movements of customers

Authors: Tananko I. E., Fokina N. P.

 Closed unreliable queueing network with batch movements is considered. The main result of the paper is the steady state distribution for given type queueing networks. 

Pages