Neurolinguistic identification of nonlinear dependences

A method is proposed for the identification of nonlinear dependences on the basis of a composition of a fuzzy knowledge base and a neural network. The structure of a neurofuzzy network that is isomorphic to a system of linguistic statements of the form “if-then” is specified, and analytical models for training are obtained. The efficiency of the proposed method of identification is illustrated by a computer experiment. Translatedfrom Kibernetika i Sistemnyi Analiz, No. 2, pp. 37–44, March–April, 2000     

Inventory control as an identification problem based on fuzzy logic

An approach is proposed to solving inventory control problems using information available on current demand and stock. The approach is based on identification of nonlinear dependences using fuzzy knowledge bases. By tuning a fuzzy model against a learning sample, model control actions can be made very close to an expert’s decision. This approach can further be developed by creating adaptive (neuro-fuzzy) inventory control models for enterprises and trading companies. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 123–133, May–June 2006.     

Efficient coding of labeled directed acyclic graphs

 We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0,…,a _n −1}, where a _n is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a _n and a _n,q , i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree. RID="*" ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF. I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading the paper very carefully and for the helpful comments.     

Identification of a nonlinear dependence by a fuzzy knowledgebase in the case of a fuzzy training set

This paper generalizes the method of identification of nonlinear dependences by a fuzzy knowledgebase to the case of fuzzy training sets. In such a set, terms are used to estimate inputs. The computer experiments performed showed that the fuzziness of experimental data is no obstacle to identification. The use of fuzzy training sets allows one to apply the proposed method to the identification of "input-output" dependences in medicine, economics, sociology, politics, and other areas in which experimental data are based on expert judgments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 17–24, March–April 2006. An erratum to this article is available at .     

Modeling individual multifactor estimation using GMDH elements and genetic algorithms

A method is proposed for comparative structural-parametric identification of a model of individual multifactor estimation. An experimental solution to this problem is obtained using evolutionary methods. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 151–159, January–February 2007.     

Isomorphism of regular NM-graphs of degree 4

An analysis of the problem of isomorphism of natural modular graphs is continued. New results are obtained for regular graphs of degree 4. The general approach to the analysis of arbitrary regular NM-graphs is developed, which brings close to solving the isomorphism problem for a given class of numerical graphs. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 95–103, January–February 2006.     

Distribution-Free Connectivity Testing for Sparse Graphs

We consider distribution-free property-testing of graph connectivity. In this setting of property testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain, and the testing algorithm has an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, and testers were shown for very few properties. However, no distribution-free property testing algorithm was known for any graph property. We present the first distribution-free testing algorithms for one of the central properties in this area—graph connectivity (specifically, the problem is mainly interesting in the case of sparse graphs). We introduce three testing models for sparse graphs:

Recognition of fractal graphs

Definitions of prefractal and fractal graphs are introduced, and they are used to formulate mathematical models in different fields of knowledge. The topicality of fractal-graph recognition from the point of view of fundamental improvement in the efficiency of the solution of algorithmic problems is emphasized. The class of polynomial algorithms for recognition of the prefractality of those graphs is proposed and rigorously substantiated. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 72–89, July–August, 1999.     

Sorting-based localization and stable computation of zeros of a polynomial. II

The stability of a sorting-based scheme for identifying polynomial zeros under coefficient perturbation is discussed. A method is proposed for simultaneous reconstruction (with a logarithmic estimate of time complexity) of the coefficients of an arbitrary polynomial from the values of its zeros. The method of identification of polynomial zeros is based on the operator of localization of extremal elements of a numerical sequence after its preliminary sorting. The method is extended to pattern recognition. Part I of this article is published in No. 1 (2007). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 161–174, March–April 2007.     

A nonlinear compromise scheme in multicriteria evaluation and optimization problems

The concept of a nonlinear compromise scheme in multicriteria problems of evaluation and optimization is presented. It is shown that the problem is to approximate correctly the utility function and construct a substantial mathematical model (scalar convolution) adequate to the given situation to solve various multicriteria problems. In analysis problems, this convolution is an objective function. Its extremization results in a compromise-optimal vector of arguments. An illustrative example is given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 106–114, July–August 2009.     

Structural models of algorithms in problems of applied programming. I. Formal algorithmic structures

A structural approach to modelling algorithms is proposed. The concept of an algorithmic structure with operations over algorithms is introduced. Models of algorithms constructed from algorithmic structures reflect aspects of algorithm representation and execution. Examples of structural and path models of algorithms are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 3–14, May-June 2009.     

Means of supporting the solution of differential equations in problem of supply-and-demand macroanalysis

This paper deals with models of demand-supply problems. A scheme of virtually organized computer support of the solution of such problems is discussed. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 174–183, July–August, 1999.     

Recognition of directed acyclic graphs by spanning tree automata

In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series–parallel graphs or generalized series–parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time.     

New quadratic models for the maximum weighted cut problem

New quadratic models are proposed to improve the upper-bound estimates in the maximum weighted cut problem. They are found by two original methods for deriving redundant quadratic constraints. A well-known linear model is shown to follow from the models proposed. Recommendations on how to develop its strengthened analogs are given. This study is partially sponsored from the grant UM2-2574-KV-03 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 63—75, January–February 2006.     

Statement and solution of some problems on a mathematical safe

The problem on a mathematical safe is formulated and studied in terms of graph theory. The cases of simplest digraphs such as paths, contours, and doubly connected components are analyzed. A number of statements on the existence of solutions to these problems are proved. The results obtained are extended to the case of corresponding nondirected graphs. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 3–14, May–June 2006.     

Privacy-preserving authentication of trees and graphs

Secure data sharing in third-party environments such as the cloud requires that both authenticity and confidentiality of the data be assured, especially when such structures encode sensitive information (such as in XML documents). Existing authentication schemes for trees and directed acyclic graphs (DAGs) are authenticity-preserving, but not confidentiality-preserving, and lead to leakage of sensitive information during authentication. In this paper, we propose a family of three leakage-free authentication schemes for (1) tree data structures, (2) directed acyclic graphs (DAGs), and (3) graphs (with cycles), which are also efficient. This family of schemes referred to as the “structural signatures” is based on the structure of the tree as defined by tree traversals and aggregate signatures. We also show through complexity and performance analysis that our scheme is practical in terms of the cost for authentication of data. We have also discussed two applications of the proposed scheme: (1) automatic correction and recovery from structural errors, and (2) secure publish /subscribe of XML documents.     

Minimal separators in dependency structures: Properties and identification

This paper considers some properties of (locally) minimal separators in oriented graphical dependency models, i.e., in Bayesian networks, Gaussian networks, and hybrid networks. Statements and rules are inferred from the criterion of d-separation and acyclic property of digraph. Necessary conditions are established that should be satisfied by members of (locally) minimal separators. Patterns of evidences are found that allow one to identify the presence or absence of an edge without an extensive search for a separator. These means facilitate the efficient inference of a model structure with the help of constraint-based algorithms. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 17–32, November–December 2008.     

Problems on mathematical safes on graphs

For given two sets of locks, the corresponding problems on mathematical safes are formulated on graphs. In the first set, all the locks have the same number of sates and, in the second set, any pair of locks can consist of different numbers of sates. A number of conditions are obtained under which there exist solutions to these problems for safes specified on directed or undirected single graphs such as a path, a chain, a cycle, and a star. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 14–21, September–October 2006.     

Dynamic models of parallel computations for macropipelined programs

Conclusion We have considered dynamic models of parallel computations and transformation algorithms for macropipelined programs that increase the internal exchange asynchronism of the parallel components. The models generalize the well-known CSP synchronous exchange paradigm (the rendezvous mechanism) [18] and provide a theoretical justification for the development of a whole range of interconnected semantic models of asynchronous computation with increasing degree of exchange asynchronism. Some publications ensure asynchronous exchange only by buffering [15, 16]. The dynamic model approach developed in this study combines buffering and analysis of data dependences of the exchange operators. It not only reduces losses associated with synchronization of communicating parallel processes, but also ensures automatic resolution of some classes of data exchange deadlocks. Experience with dynamic models as a means of increasing the efficiency of macropipelined programs and multilevel memory in multiprocessor systems [12, 17] can be applied in other programming systems and parallel program design systems of both compiling (S1, S2) and interpreting (S3) type. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 45–65, November–December, 1995.     

A self-organizing map for adaptive processing of structured data

Recent developments in the area of neural networks produced models capable of dealing with structured data. Here, we propose the first fully unsupervised model, namely an extension of traditional self-organizing maps (SOMs), for the processing of labeled directed acyclic graphs (DAGs). The extension is obtained by using the unfolding procedure adopted in recurrent and recursive neural networks, with the replicated neurons in the unfolded network comprising of a full SOM. This approach enables the discovery of similarities among objects including vectors consisting of numerical data. The capabilities of the model are analyzed in detail by utilizing a relatively large data set taken from an artificial benchmark problem involving visual patterns encoded as labeled DAGs. The experimental results demonstrate clearly that the proposed model is capable of exploiting both information conveyed in the labels attached to each node of the input DAGs and information encoded in the DAG topology.