The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable) parallel systems with simple single–bit processing elements and vertical processing. The associative algorithm is represented on the STAR–machine as the main procedure DeleteArcSPT that uses some auxiliary procedures. By means of the auxiliary procedures, we execute some parts of the associative parallel algorithm for dynamic update of the shortest paths tree after deleting an arc from the graph. We prove correctness of the procedure DeleteArcSPT and all its parts. We obtain that on the STAR–machine this procedure takes O(hk) time, where h is the number of bits required for coding the maximum of the shortest paths weights and k is the number of vertices, whose shortest paths change after deleting an edge from the given graph.  

The article considers the problem of estimating autoregressive model parameters of elementary speech units such as phonemes. It is suggested an iterative algorithm based on the Newton numerical minimization technique to search an autoregressive model of phonemes specified its multiple samples. For this purpose the analytical expressions of the gradient and the Hessian of Kullback–Leibler information divergence between autoregressive models were computed. Experimental studies on a set of English phonemes showed that the developed algorithm requires less computational effort for large amounts of data, and iterations count depends little on the amount of input data as opposed to reference phoneme selection algorithm based on the criterion of a minimum sum of information divergence. Moreover, the proposed algorithm allows finding models of phonemes, which provide a higher probability of correct recognition.

We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are n ≥ 2 autonomous robots, that need to agree without outside interference on distribution of shelters, so that straight pathes to the shelters will not intersect. The problem is closely related to the assignment problem in Graph Theory, to the convex hull problem in Combinatorial Geometry, or to the path-planning problem in Artificial Intelligence. Our algorithm grew up from a local search solution of the problem suggested by E.W. Dijkstra. We present a multiagent anonymous and scalable algorithm (protocol) solving the problem, give an upper bound for the algorithm, prove (manually) its correctness, and examine two communication aspects of the RinS problem — the informational and cryptographic. We proved that (1) there is no protocol that solves the RinS, which transfers a bounded number of bits, and (2) suggested the protocol that allows robots to check whether their paths intersect, without revealing additional information about their relative positions (with respect to shelters). The present paper continues the research presented in Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) (by E.V. Bodin, N.O. Garanina, and N.V. Shilov), published in Modeling and analysis of information systems, 18(2), 2011.

The problem of integer balancing of a three-dimensional matrix with constraints of second type is studied. The elements of the inner part (all three indices are greater than zero) of the three-dimensional matrix are summed in each direction and each section of the matrix; the total sum is also found. These sums are placed into the elements where one or more indices are equal to zero (according to the summing directions). The problem is to find an integer matrix of the same structure, which can be produced from the initial one by replacing the elements of the inner part with the largest previous or the smallest following integer. At the same time variations of the sums of elements from that in the initial matrix should be less than 2 and the element with three zero indices should be produced with standard rules of rounding-off. Some solvability classes for this problem are defined. Also, a model of reducing this problem to a problem of finding the maximum flow in a multiple network and an algorithm for the corresponding flow problem are suggested. A polynomial algorithm for the particular case of n = 2 is described.

In this paper we consider a new approach for domain-specific opinion word extraction in the Russian language. We propose a set of statistical features and an algorithm combination that can extract opinion words in a particular domain. The extraction model was trained in the movie domain and then applied to four other domains. The quality of the obtained sentiment lexicons was evaluated intrinsically on the base of an expert markup and remained on the high level during the model transfer to various domains. Finally, our method is adapted to the movie domain in English and it demonstrated good results.

The paper presents a novel approach to finding regional scopes (geotagging) of websites. Unlike the traditional approaches, which generally involve training a separate classification model for each class (region), the proposed method is based on training a single model which is used for all regions of the same type (e.g. cities). This approach is made possible by the usage of ”relative” features which indicate how a selected region matches up to other regions for a given website. The classification system uses a variety of features of different nature that have not been yet used together for machine-learning based regional classification of websites. The evaluation demonstrates the advantage of our ”one model per region type” method versus the traditional ”one model per region” approach. A separate experiment demonstrates the ability of the proposed classifier to successfully detect regions which were not present in the training set (which is impossible for traditional approaches).

Petri net is said to be elementary if every place can contain no more than one token. In this paper, it is studied topological properties of the elementary Petri net for a pipeline consisting of n functional devices. If the work of the functional devices is considered continuous, we can come to some topological space of “intermediate” states. In the paper, it is calculated the homology groups of this topological space. By induction on n, using the Addition Sequence for homology groups of semicubical sets, it is proved that in dimension 0 and 1 the integer homology groups of these nets are equal to the group of integers, and in the remaining dimensions are zero. Directed homology groups are studied. A connection of these groups with deadlocks and newsletters is found. This helps to prove that all directed homology groups of the pipeline elementary Petri nets are zeroth.

A new approach to construction of reliable discrete PLC-programs with timers — programming based on specification and verification — is proposed. Timers are modelled in a discrete way. For the specification of a program behavior we use the linear-time temporal logic LTL. Programming is carried out in the ST-language according to a LTLspecification. A new approach to programming of PLC is shown by an example. The proposed programming approach provides an ability of a correctness analysis of PLC-programs using the model checking method. The programming requires fulfillment of the following two conditions: 1) a value of each variable should be changed not more than once per one full PLC-program implementation (per one full working cycle of PLC); 2) a value of each variable should only be changed in one place of a PLC-program. Under the proposed approach the change of the value of each program variable is described by a pair of LTL-formulas. The first LTL-formula describes situations that increase the value of the corresponding variable, the second LTL-formula specifies conditions leading to a decrease of the variable value. The LTL-formulas (used for specification of the corresponding variable behavior) are constructive in the sense that they construct the PLC-program, which satisfies temporal properties expressed by these formulas. Thus, the programming of PLC is reduced to the construction of LTL-specification of the behavior of each program variable.

Suppose we are given a bisingular initial boundary-value problem for a system of parabolic equations that contains a small parameter ε² at the second derivative and √ ε at the first derivative with respect to the spatial variable. We prove an asymptotics of any order for the solution of the problem with respect to the small parameter, without using the joining of asymptotic expansions. To this end, we apply an asymptotic method of differential inequalities. The essence of the method is to use the formal asymptotics (given in the previous paper) for constructing lower and upper solutions of the problem. By modifying the last terms of order εⁿ⁄² in the partial sum of the formal asymptotics, we construct the lower and the upper solutions, between which the exact solution of the problem lies.

This article is about the Augmented Reality technology itself and its current implementations. In the first part of the article the authors give a short historical reference to the origins of the name ”augmented reality”, by whom it was introduced and what it means. Later in the article two major approaches to building AR are described. The first one is based on the usage of a marker, and the second one is marker-free. The first approach is examined in detail. In order to analyze video stream and recognize known objects in it, algorithms of the Computer Vision are used. The authors give a short description and the main characteristics only of two of them: genetic algorithms and feature detection & description. For a programmatic implementation of those algorithms one can use special libraries like OpenCV and AForge.NET, also mentioned in the article. Both of them give vast functional capabilities in image processing and object recognition. At the end of the article is given an example of creating AR using the OpenCV library. Main attention is payed to the problem of making projection of a 3D model on the marker’s plane. This example can be used as the foundation for a custom AR framework.

A class of infinite-state automata with a simple periodic behaviour and a convenient graphical representation is studied. A positive one-counter circuit is defined as a strongly connected one-counter net (one-counter nondeterministic finite automata without zero-testing) with at least one positive cycle. It is shown that in a positive circuit an infinite part of a reachability set is an arithmetic progression; numerical properties of this progression are estimated. A specific graphical representation of circuits is presented. General one-counter nets are equivalent to Petri Nets with at most one unbounded place and to pushdown automata with a single-symbol stack alphabet. It is shown that an arbitrary one-counter net can be represented by a finite tree of circuits. A one-counter net is called sound, if a counter is used only for “infinite-state” (periodic) behaviour. It is shown that for an arbitrary one-counter net an equivalent sound net can be effectively constructed from the corresponding tree of circuits.

The images built on the basis of rectangular and hexagonal lattices are discussed in the article. For images on a rectangular lattice a formula is proposed, which gives approximate values of the components of a characteristic set of coefficients when turning at an arbitrary angle by the method of the nearest neighbor. The characteristic sets are presented in the form of diagrams, an experimental evaluation of errors is made. It was confirmed a good agreement with the predicted value component of characteristic sets and those which were obtained experimentally. For images built on the basis of a hexagonal lattice was offered a similar formula for the approximation of the components of the characteristic set for rotating at any angle, when this was applied to the modification of the nearest neighbor method for the preservation of coherence, as it was discovered its violation in some cases on a hexagonal lattice. On the basis of four-pixel fragments are built diagrams, which show a good agreement of predicted values and the obtained ones in the experiment. It was defined a system of three-pixel hexagonal fragments to which the theorem is proved on the Eulerian characteristic and were offered analytical expressions, which allow to avoid experimental detection of the characteristic sets of coefficients for all possible reference angles. Their use requires to produce only one such experiment.

This paper presents the description of a possible way to build the universal linearized control flow graph which is supposed to be architecture-independent and applicable to the description of any high level language programs. The practical usefulness of the graph considered is the existence of the fast and optimal search of the unique execution paths that is valuable in the methods of static code analysis of algorithms for race condition search. Optimizing compiler CLANG&LLVM is used as a technical tool for building a linearized control flow graph. The analysis of LLVM compiler procedural optimizations is carried out in the article. Transformations of intermediate representation of those optimizations result in reduction of the number of instructions responsible for conditional or unconditional branches in the code as well as the elimination or simplification of the whole loops and conditional constructions. The results of the analysis performed in the paper allowed revealing the most effective optimizations line of the LLVM compiler, which leads to a significant linearization of the control flow graph. That fact was demonstrated by the example code of the Peterson mutual execution algorithm for 2 threads.

We consider the problem of the nonparametric entropy estimation of a stationary ergodic process. Our approach is based on the nearest-neighbor distances. We propose a broad class of metrics on the space Ω = A^N of right-sided infinite sequences drawn from a finite alphabet A. The new metric has a parameter which is a non-increasing function. We apply this metrics to nearest-neighbor entropy estimators. We prove that, under certain conditions, the estimators has a small variance. We show that a special selection of the metric parameters reduction of the estimator’s bias. The article is published in the author’s wording.