Preview

Modeling and Analysis of Information Systems

Advanced search
Vol 24, No 2 (2017)
View or download the full issue PDF (Russian)

Articles

125-140 10031
Abstract

Process mining is a relatively new field of computer science, which deals with process discovery and analysis based on event logs. In this paper we consider the problem of discovering a high-level business process model from a low-level event log, i.e. automatic synthesis of process models based on the information stored in event logs of information systems. Events in a high-level model are abstract events, which can be refined to low-level subprocesses, whose behavior is recorded in event logs. Models synthesis is intensively studied in the frame of process mining research, but only models and event logs of the same granularity are mainly considered in the literature. Here we present an algorithm for discovering high-level acyclic process models from event logs and some specified partition of low-level events into subsets associated with abstract events in a high-level model.

141-154 11008
Abstract

We study the polyhedral properties of three problems of constructing an optimal biclique in a bipartite graph. In the first problem we consider a balanced biclique with the same number of vertices in both parts and arbitrary edge weights. In the other two problems it is required to find maximum or minimum unbalanced bicliques with a fixed number of vertices and non-negative edges. All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. We describe the adjacency criterion in the 1-skeleton of the balanced biclique polytope. Clique number of 1-skeleton is estimated from below by a superpolynomial function. For both unbalanced biclique problems we establish the superpolynomial lower bounds on the clique numbers of the graphs of non-negative cone decompositions. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.

155-167 12653
Abstract

Null values have become an urgent problem since the creation of the relational data model. The impact of the uncertainty affects all types of dependencies used in the design and operation of the database. This fully applies to the inclusion dependencies, which are the theoretical basis for referential integrity on the data. Attempts to solve this problem contain inaccuracy in the statement of the problem and its solution. The errors in formulation of the problem can be associated with the use in the definition of untyped inclusion dependencies, which leads to permutations of the attributes, although, the attributes in database technology are identified by name and not by their place. In addition, linking with the use of the inclusion dependencies of heterogeneous attributes, even of the same type, is a sign of lost functional dependencies and leads to interaction of inclusion dependencies and non-trivial functional dependencies. Inaccuracies in the solution of the problem are contained in the statements of axioms and the proof of their properties, including completeness. In this paper we propose an original solution of this problem only for typed inclusion dependencies in the presence of Null values: a new axiom system is proposed, its completeness and soundness are proved. On the basis of inference rules we developed an algorithm for the construction of a not surplus set of typed inclusion dependencies. The correctness of the algorithm is proved.

168-185 9414
Abstract

The article considers bifurcation problems for a logistic equation with delay at small perturbations. The most interesting results are for the case when small perturbations contain a large delay. The main results are special nonlinear equations of evolution in the normal form. Their nonlocal dynamics defines the behaviour of the solutions of the original equation in a small neigbourhood of the balance state or the cycle. It turns out that the order of large delay magnitude is principal. For the simplest case, when this order is congruent with the magnitude inverse to the small parameter appearing in the equation, the normal form is a complex equation with delay. In the case when the order of the delay coefficient is even higher, the normal form is presented by a multiparameter family of special boundary-value problems of degenerate-parabolic type. All these things allow to make a conclusion about the fact that in the considered problems with large delay the multistability is typical.

186-204 1101
Abstract

In this paper the mathematical model of a neural network with a ring synaptic interaction elements is considered. The model is a system of scalar nonlinear differential-difference equations, the right parts of which depend on a large parameter. The unknown functions included in the system characterize the membrane potentials of the neurons. The search of relaxation cycles within the system of equations is interested. To this end solutions of the task are finded in the form of discrete traveling waves. It allows to research a scalar nonlinear differential-difference equations with two delays instead of system. Further, a limit a object that represents a relay equation with two delays is defined by large parameter tends to infinity. There are six cases of restrictions on the parameters. In every case exist alone periodic solution of relay equation started from initial function from suitable function class. It is structurally proved by using the step method. Next, the existence of a relaxation periodic solutions of a singularly perturbed equation with two delays is proved by using Poincare operator and Schauder principle. The asymptotics of this solution is constructed, and then it is proved that the solution is close to decision of the relay equation. Because of the exponential estimate Frechet derivative of the Poincare operator implies the uniqueness and stability of solutions of differential-difference equation with two delays.

205-214 9839
Abstract

We investigate interrelations between the Tate conjecture for divisors on a fibred variety over a finite field and the Tate conjecture for divisors on the generic scheme fibre under the condition that the generic scheme fibre has zero irregularity. Let \(\pi:X\to C\) be a surjective morphism of smooth projective varieties over a finite field \(F_q\) of characteristic \(p\), \(C\) is a curve and the generic scheme fibre of \(\pi\) is a smooth variety \(V\) over the field \(k=\kappa(C)\) of rational functions of the curve \(C\), \(\overline k\) is an algebraic closure of the field \(k\), \(k^s\) is its separable closure, \(NS(V)\) is the N\'eron - Severi group of classes of divisors on the variety \(V\) modulo algebraic equivalence, and assume that the following conditions hold: \(H^1(V\otimes\overline k,\mathcal O_{V\otimes\,\overline k})=0,\) \(NS(V)=NS(V\otimes\overline k).\) If, for a prime number \(l\) not dividing \({Card}([NS(V)]_{tors})\) and different from the characteristic of the field \(F_q\), the following relation holds \(NS(V)\otimes\Bbb Q_l\,\,\widetilde{\rightarrow}\,\,[H^2(V\otimes k^{sep},Q_l(1))]^{Gal( k^{sep}/k)} \) \((\)in other words, if the Tate conjecture for divisors on \(V\) holds\()\), then for any prime number \(l\neq charr(F_q)\) the Tate conjecture holds for divisors on \(X\): \(NS(X)\otimes Q_l\,\,\widetilde{\rightarrow} \,\,[H^2(X\otimes\overline F_q,Q_l(1))]^{Gal(\overline F_q/F_q)}.\) In  particular, it follows from this result that the Tate conjecture for divisors on an arithmetic model of a \(K3\) surface over a sufficiently large global field of finite characteristic different from 2 holds as well.

215-226 1295
Abstract

Prevention of data loss from digital media includes such a process as a backup. It can be done manually by copying data to external media or automated on a schedule by using special software. There are the remote backup systems, when data are saved over the network to the remote repository. Such systems are multi-user and they process large amounts of data. Shared storage can meet files containing the same fragments. The elimination of repeated data is based on the mechanism of de-duplication. It is a method of information compression, when the search of copies is performed in the entire dataset rather than within a single file. The main advantage of using this technology is a significant saving of disk space. However, the mechanism of eliminating repetitive data can significantly reduce the speed of saving and restoring information. This article is devoted to the problem of implementing such a mechanism in the backup system with information storage in a relational database. In this paper we consider an example of implementation of such a system working in two modes: with the de-duplication of data and without it. The article illustrates a class diagram for the development of a client part of application as well as the description of tables and relationships between them in a database that belongs to the backend. The author offers an algorithm of saving data wiht de-duplication, and also gives the results of comparative tests on the speed of the algorithms of saving and restoring information when working with relational database management systems from different manufacturers.

227-238 915
Abstract

The problems of nonlinear programming, criteria and limitations depend on the variables averaged. It is shown that if these problems have solutions, the Lagrangian reaches the maximum for the variables, which are averaged. The functions defining the problem can not be differentiable and continuous on these variables, the set of possible values may contain isolated points. In variational problems there can be no solution in the class of piecewise continuous functions of the variables, but there can be a generalized solution in which these variables change in the sliding mode, and the optimality criterion tends to its upper edge. If in such problems the solution in the class of piecewise - continuous functions exists, the conditions of optimality of this solution are in the form of the Hamiltonian function of the maximum principle. The relationship between the average over time and across multiple variables is considered.

239-252 1322
Abstract

For the practical application of code cryptosystems such as McEliece, it is necessary that the code used in the cryptosystem should have a fast decoding algorithm. On the other hand, the code used must be such that finding a secret key from a known public key would be impractical with a relatively small key size. In this connection, in the present paper it is proposed to use the tensor product \( C_1 \otimes C_2 \) of group \(\textrm{MLD}\) codes \( C_1 \) and \( C_2 \) in a McEliece-type cryptosystem. The algebraic structure of the code \( C_1 \otimes C_2 \) in the general case differs from the structure of the codes \( C_1 \) and \( C_2 \), so it is possible to build stable cryptosystems of the McEliece type even on the basis of codes \( C_i \) for which successful attacks on the key are known. However, in this way there is a problem of decoding the code \( C_1 \otimes C_2 \). The main result of this paper is the construction and justification of a set of fast algorithms needed for decoding this code. The process of constructing the decoder relies heavily on the group properties of the code \( C_1 \otimes C_2 \). As an application, the McEliece-type cryptosystem is constructed on the code \( C_1 \otimes C_2 \) and an estimate is given of its resistance to attack on the key under the assumption that for code cryptosystems on codes \( C_i \) an effective attack on the key is possible. The results obtained are numerically illustrated in the case when \( C_1 \), \( C_2 \) are Reed--Muller--Berman codes for which the corresponding code cryptosystem was hacked by L. Minder and A. Shokrollahi (2007).



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)