Volume 16, issue 1-4, 2012

Part 1. General problems of the theory of intelligent systems

• Abrosimov V.K., Demidov R.S.. Information landscape of the organization.
  New concepts needed for the analysis of selection and implementation information systems effectiveness – the information landscape, the compatibility and the consistency, the necessity and sufficiency of information resource have introduced and discuss. It is shown that with its sharing it is easy and methodically reasonably to choose the most effective and potentially demanded for business information system from a group of such systems with different characteristics
  Keywords: information system, information resource, selection, implementation efficiency, landscape
• Lebedev A.A.. Synthesis of information aggregation operators based on expert descriptions.
  The problem of selecting an aggregation function, a function describing the behaviour of one element of a system relative to others, is omnipresent in developing information gathering and analysis systems. In this paper, we develop an approach to describe k-valued logic functions by fuzzy constraints. We prove that the general problem of defining a function by fuzzy constraints is NP-complete and also provide polynomial algorithms solving the problem in several special cases.
  Keywords: selecting aggregation functions, fuzzy constraints
• Toprover G.L., Kiselev S.L.. Simulation model of computer analysis of facts.
  The article presents a simulation-driven formal model for computer-aided facts analysis based on the pattern recognition theory methods.
  Keywords: knowledge management, factology, factography, facts analysis
• Chmyr I.A.. Natural Dialogue: Modeling a Dialogue Transaction in the Context of Knowledge Representation.
  The paper deals with an investigation and modeling of dialogue and dialogue transactions. An ontological model of human dialogue interaction, underlying follow-up reasoning, is obtained on the basis of analysis of human-human dialogues and illustrated by one of Plato’s dialogue Protagoras. In the sequel, attention is focused on one type of human-human dialogues, called erotetic dialogue and on the structure of erotetic dialogue transaction from the viewpoint of knowledge interchange within the transaction. A spectrum of formal models, oriented towards discovering the inner logical structure of erotetic transaction is offered. The distinguishing feature of all models is their orientation on language-independent entities representing declarative knowledge associated with a transaction’s elements.
  Keywords: ontological dialogue model, erotetic dialogue, dialogue transaction, declarative knowledge, Language of Ternary Description

Part 2. Special issues of the theory of intelligent systems

• Zubyuk A.V.. Likelihood ratio criterion in random morphology.
  Classification of images with random forms and search for an object, which images have random form, on an undefined background are considered. Method of solving those problems based on the likelihood ratio principle is suggested. A variant based on the possibility theory will be considered in the further publication.
  Keywords: morphological image analysis, random form of images, likelihood ratio criteria
• Nazarov A.N.. On the assessment of the number of virtual connections and high-quality delivery of data traffic in cellular mobile networks using GPRS technology.
  On the basis of development of Entropy approach the optimising model of calculation of number of virtual connections and optimising model of calculation of number of virtual connections with the set quality of service of the traffic are developed, allowing to estimate resource maintenance of the central equipment and data transmission paths in cellular networks of a mobile communication on technology GPRS. Varied parametres of model with the set quality of service of the traffic are values of pass-bands of the bit traffic of various categories. Calculations on the developed models are reduced to the consecutive decision of joint systems of the linear equations.
  Keywords: GPRS, GGSN, SGSN, QoS, optimising model
• Pivovarov A.P.. Functional complexity of the counting problem for the two-dimensional dominance problem.
  This paper considers 2-dimensional dominance counting problem. Three types of algorithms that solve this problem are constructed in terms of information graph data model. Required space and worst case time are estimated for them. Fractional cascading technique is used as one of tools to reduce processing time at the cost of increased required space.
  Keywords: 2-dimensional dominance counting, computational information graph, information graph, functional complexity, fractional cascading
• Snegova E.A.. A criterion for the reducibility of the problem of dangerous proximity to one-dimensional problems for polynomial laws of motion.
  In this paper we consider Moving objects closeness problem (MOC problem) for the case of polynomial laws of motion. For this case we present and prove criteria for reducibility of the MOC problem to one-dimensional problems range searching problem and one-dimensional stabbing problem.
  Keywords: databases of moving objects, spatio-temporal databases, information graph, complexity
• Timirova A.N.. Properties of the Markowitz model when specifying parameters by means of fuzzy set theory.
  This work presents the analysis of expected return and risk of assets based on portfolio selection model. Expected return is presented as a fuzzy number and risk – as fuzziness degree of expected return.
  Keywords: fuzzy number, fuzziness degree, Markowitz model, investment portfolio
• Titova E.E.. Linear-in-time image construction by cellular automata.
  The work deals with the problem of image construction with a cellular automata on a rectangular screen. For cases where an elementary automaton has 3, 4 and 5 states were developed algorithms with time linear to the screen resolution. There were founded estimates of the image construction time with an increasing number of elementary automaton states. An algorithm of image construction for the screen with only one free input was developed.
  Keywords: cellular automaton, generator, universal screen, image construction, estimation for time of image construction
• Tsymzhitov D.N.. On a new approach to solving the problem of soft ML decoding of linear codes.
  In this paper we present a method of decoding of binary linear codes based on the use of vectors, which we call irreducible. Irreducible vector represents the minimum structure of a certain type and is a generalization of the minimum codeword concept. We propose two algorithms that implement this approach for two classes of codes, which are defined by certain assumptions about the structure of their Tanner graph. In the first case, we consider codes with an acyclic Tanner graph, and in the second case, we consider codes with a Tanner graph in which all variable nodes have degree at most 2. If n is the length of the code, the first algorithm runs in O(n²) time, whereas the second one runs in O(n⁴) time.
  Keywords: soft-decision decoding, maximum-likelihood decoding, linear block codes, decoding complexity, minimal codewords

Part 3. Mathematical models

• Bokk N.G.. On the order of an element in a group of automaton substitutions.
  We build a group automaton of 2n order for each natural n. We also introduce a criterion of order definition for automata with Abelian intrinsic groups by group generators. Finally we show that such criterion is impossible in general case.
  Keywords: automaton permutations, group automata, intrinsic semigroup, automaton order
• Ishmatova Yu.A.. On some properties of groups of algebras with parameters.
  Groups of algebras with parameters are the main object of cryptographic standards of Uzbekistan. We investigate a number of cryptographically essential properties of such groups. We prove reversibility criterion, evaluate group order and show correspondence of exponentiation with parameter and exponentiation in residue rings.
  Keywords: algerbas with parameters, cryptographic standards, exponentiation
• Perper E.M.. On the functional complexity of substring search.
  The paper deals with the problem of search subwords in set of words. This problem is as follows: suppose we are given a set of words; in this set for an arbitrary subword we must find words which contain this subword. In this paper, three algorithms of search are developed and, with them, estimates of the functional complexity of search are obtained.
  Keywords: word, subword, search, information graph, complexity, volume
• Pivovarov A.P.. On one method for obtaining lower bounds for the complexity of information graphs.
  This paper contains one method for obtaining of lower bounds for complexity of information graphs of different types (in average and in the worst case). For this purpose the notion of general information graph is introduced. This notion covers the majority of information graph modifications. The notion of general information graph acceptability for a output function is introduced. The estimates obtained for some general information graph depend on the codomain cardinality of the output function.
  Keywords: general information graph, lower bound for complexity, search modelling
• Rodin A.A.. On the continuity of the set of special precomplete classes in the set of automaton mappings.
  Let D be a closed class in k-valued logic. Denote by P(D) the set of deterministic finite functions having k-valued function from D in every state. It is shown in the article, that there exists continuum of precomplete classes C such that C includes P(D).
  Keywords: automata mappings, precomplete class, K-valued logic
• Sokolov A.P.. On the complexity of the restructuring of formal neurons.
  Problems of neurons learning complexity are considered in this paper. Threshold function act as mathemetical model of neuron. Following problem is being studied: what is the complexity of mutual reconstruction (learning) of pairs of threshold functions in the worst case, in most cases and inside sets of threshold functions that are invariant by groups of permutations. Threshold functions are defined by means of linear forms with integer coefficients. Number of elementary operations over weight coefficients of the linear form is the measure of complexity of mutual reconstruction of threshold functions. Set of upper and lower bounds for complexity of mutual reconstruction of formal neurons for various cases was found. It was developed an algorithm for reconstruction of given formal neuron to the desired one. Time complexity of this algorithm was estimated.
  Keywords: threshold functions, learning complexity of neural networks