Volume 12, issue 1-4, 2008

Part 1. General problems of the theory of intelligent systems

• S.A. Vasilyev. Artificial Intelligence for an Autonomous Discrete System. Today there is no universally accepted definition of "Artificial Intelligence". Perhaps that is why there is no general solution to the problem of its creation. The author of this article tried to "narrow" the problem, namely to consider aspects of intelligent behavior of autonomous discrete system (ADS)
  Keywords: artificial intelligence, intelligent system
• A.V. Chechkin, A.E. Evgrafov, V.V. Rozhkov, M.V. Pirogov. Symbolic model of the problem area of ​​a complex system – the basis for intellectualizing such a system using the example of the automated control system. The successes of modern complex systems, software and hardware (SHT) and the scale of their distribution are well known. However, information constantly appears from various sources indicating numerous and diverse problems of the complex systems used. Is there a problem of modern complex systems that can be defined as the main and fundamental one? If so, what does it consist of?
  Keywords: Intelligent system, model

Part 2. Special issues of the theory of intelligent systems

• V.A. Gazaryan, Yu.M. Nagorny, Yu.P. Pytiev, A.K. Shakhovskaya. On the theoretical-possibility methods for solving problems of medical diagnostics. It is shown that for solving many problems of medical diagnostics it is natural to use not a probabilistic, but a possibilistic model of analysis and interpretation of data [1, 2], obtained both with the use of modern medical technologies and reflecting the well-being and condition of the patient, professional experience and intuition of the doctor. A possibilistic model of disease symptomatology is constructed, characterizing the fuzzy connection between the symptomatic description of the patient's condition and his actual condition, in which the diagnostic criteria are determined by groups of feature values ​​(symptoms), ranked by the values ​​of their possibilities for a given disease. In the possibilistic model of diagnostics, the optimal decision rule minimizes the possibility and (or) inevitability of losses when making a diagnosis.
  Keywords: medicine, diagnostics, medical diagnostics
• A.V. Rozanov. Modeling of a plane rectilinear motion in a homogeneous structure. The paper considers the problem of modeling uniform rectilinear motion with reflection from obstacles using homogeneous structures. The concept of a discrete trajectory is introduced, a one-to-one correspondence between discrete and continuous trajectories is established. A homogeneous structure is constructed, universal for a wide class of obstacles, and it is shown that for other obstacles there is an infinite set of initial conditions of motion that do not allow modeling.
  Keywords: homogeneous structure, modeling, uniform motion
• A.P. Sokolov. On neural network implementation of aircraft control algorithms. This work is devoted to the development of a method for synthesizing a neural network that implements a predetermined computational algorithm. Algorithms used in aircraft control systems are considered. The synthesized neural network should be in some sense equivalent to the original algorithm. This means that the behavior of the neural network for the entire control system as a whole should not differ from the behavior of the original computational procedure. It is assumed that the original algorithm (computational procedure) is implemented in some programming language, for example C++.
  Keywords: neural network, neural network, aircraft
• E.E. Titova. Construction of images by cellular automata. The work deals with the problem of image construction with cellular automata on a rectangular screen. It is shown that for every image is necessary and sufficient that the cellular automaton has three states. Estimates are obtained for time of image construction depending on the number of states of a cellular automaton
  Keywords: cellular automaton, generator, universal screen, image construction, estimation for time of image construction

Part 3. Mathematical models

• D.N. Babin, A.B. Kholodenko. On automata approximation of natural languages. The paper consists of two parts. The first part presents a short review of the mathematical approaches to language models, including some works of the authors. In the second part a class of regular languages with limitary frequency properties is defined and some theorems concerning this class are stated
  Keywords: finite state machine, automaton, regular expression, n-gram, bigram, trigram
• N. Yu. Volkov. On the automaton model of pursuit inside a square. The process of pursuit of several independent "victim" automata by a collection of "predator" automata is studied. Pursuit is performed in a square with side l. We show that for an arbitrary finite set of independent "victims" there exists a finite collection of "predators" that "catches" all victims in the given set for arbitrary l, arbitrary initial positions of all "victims" and arbitrary starting point of "predators" (all "predators" start from the same position). We also show that for an arbitrary finite collection of "predators" there exists a natural number l such that for an arbitrary initial position of "predators" in a square with side l there exists a set of independent "victims" such that "victim" speed is less that "predator" speed, "victim" view is less than "predator" view, and an initial position of "victims" in the same square such that all victims "escape" from "predators".
  Keywords: pursuit, maze, periodical behavior, independent automata system, collection of automata
• B.V. Voronin, V.V. Osokin. On the complexity of deciphering the essential variables of a function defining a partition of a Boolean cube. In the current paper we analyze the complexity of learning relevant variables of some subclass of functions splitting Boolean cube into cube faces. We show that k*log₂n membership queries is enough to learn all relevant variables of any function in this class. We obtain asymptotics of relevant variables learning complexity in the cases of small and big values of k: log₂n and n correspondingly
  Keywords: variable learning complexity, Boolean cube splitting, attribute-efficient learning, learning juntas, pseudo-boolean functions, exact learning model
• Yu. G. Geraskina. Automated model of substance transport through the lungs in polluted environments. In the work an automaton model of mechanism of substance transportation in lungs is offered (the automaton model of transportation is АМТ). Cases of operation of АМТ in contaminated stationary medium, as well as in nonstationary are considered. For each case the following problems are settled: for a corresponding automaton the number of states in it and diameter of his Moore diagramm are estimated, start-up states are described and their number is found, the average depth of a diagramm is found, the criterion of a transition of some state into another is specified and time of such transition is appreciated, final states are described and their number is appreciated.
  Keywords: automaton, automaton model, Moore diagram, state of an automaton, transportation of substance, lungs, bronchi
• D.N. Zhuk. On the Unsolvability of the Completeness Problem for Definite Automata. In this paper we consider the sets F U nu of definite automata, where F is a fixed closed class of Boolean functions and nu is a finite set of definite automata. Some closed classes of Boolean functions such that the completeness and A-completeness problem for these sets of definite automata is unsolvable were found.
  Keywords: definite automata, completeness problem, unsolvability
• D.V. Zaitsev. On the complexity of matrix embedding. In this paper we study the complexity of universal matrices, which provide the matrix of a given class as submatrices. The complexity refers to the size of the universal matrix. Such objects are considered in dealing with de Bruijn sequences and tori.
  Keywords: matrix, matrix embedding, complexity
• V. Yu. Levin, V. A. Nosov. Analysis of the increase in cryptographic complexity of systems when switching to elliptic curves. It is well known that the main cryptographic complexity when breaking classical cryptosystems over finite fields is given by the complexity of solving the discrete logarithm problem. In the case of classical cryptosystems based on elliptic curves, such complexity is given by solving the corresponding discrete logarithm problem on an elliptic curve. It is worth noting that most cryptosystems allow switching to elliptic curves. In this case, there is a significant increase in cryptographic complexity. In this paper, an analysis of the change in complexity when switching to elliptic curves is carried out. The analysis found that the increase in complexity with such a transition does not lead to an increase in the key sizes, but an effect of reducing their lengths is observed while maintaining the overall cryptographic complexity of the system. The paper provides a theoretical justification for this fact, and constructs dependencies of key lengths.
  Keywords: elliptic curve, cryptographic system
• I.V. Lyalin. Solving automaton equations with one unknown. Let S be a digital circuit, which is consisted from finite-state machines. Let a finite-state machine x be possible to be changed to other finite-state machine x' with the same input and output alphabets. Does there exist such x' that after substitution x -> x', S will be equivalent to the finite-state machine h? The article describes the algorithm for solving this problema and describes the set of all appropriate x', depends on S and h.
  Keywords: finite-state machine, FSM, digital circuit, FSM equation
• S.V. Moiseev. On the implementation of automata by neural networks. We consider discrete time neural networks as finite automata. Unlike the classical Kleene theorem, we demonstrate that it is not every finite automaton that can be represented by a neural network (without a time delay). We provide different criteria to test whether an automaton can be represented by a neural network (with or without time delay). We also provide a criterion to test if one can change the encoding of the input and output alphabets of an automaton in order that the automaton become representable by a neural network.
  Keywords: finite automata, discrete time neural networks
• V.A. Nosov, A.E. Pankratyev. On the functional assignment of Latin squares. This paper studies functional methods for specification of Latin squares over the sets of n-dimensional Boolean vectors, n-dimensional vectors over an arbitrary finite prime field and over an arbitrary finite Abelian group. In conclusion, a method for constructing classes of non-group Latin squares is presented.
  Keywords: Latin square, Boolean vector, Abelian group
• A.P. Pivovarov. Search for a representative in the problem of metric proximity. This paper offers an algorithm to search representative record in two-dimensional metrical closeness problem. This algorithm requires O(k) memory, where k is the number of records in the library. Time-complexity of this algorithm is constant in average and O(log k) in the worst case.
  Keywords: metric, metrical closeness, но я бы добавил еще representative search
• E.A. Potseluyevskaya. Polynomial cases of solving the problem of F-satisfiability of Boolean formulas.. In this article an algorithm for S-satisfiability problem decision for boolean functions depending at most on three variables is described. The algorithm belongs to the class of DPLL-algorithms and is based on exhaustive search of certain subset S of variables x_i and on solution of polynomial 2-SAT subproblem for any fixed set of variables values. In the article the conditions when the complexity of the algorithm is a polynomial value are also shown.
  Keywords: satisfiability, S-satisgiability, algorithm, minimal set
• A.P. Sokolov. On the constructive characterization of threshold functions. Structure of the set of threshold functions and complexity problems are considered in the paper. The notion of a signature of threshold function is defined. It's shown that if threshold function essentially depends on all of its variables then signature of this function is unique. Set of threshold functions is partitioned onto classes with equal signatures. Theorem characterizing this partition is proved. Importance of the class of monotone threshold functions is emphasized. Complexity of transferring one threshold function specified by the linear form into another is examined. It's shown that in the worst case this transferring would take exponential time. Structure of the set of linear forms specifying the same threshold function is also examined. It's proved that for any threshold function this set of linear forms has unique basis in terms of the operation of addition of the linear forms. It's also shown that this basis is countable.
  Keywords: threshold functions, learning complexity of neural networks