Contents of magazine "Intelligent systems"
Volume 13, issue 1-4, 2009

Part 1. General problens of Intelligent systems theory

• К.Э. Плохотников. Математическое моделирование и вычислительный эксперимент: методология и практика (in Russian).
  
  A new approach to the methodology of (mathematical) models and computational experiments is presented. We propose a formal description of the method of (mathematical) modeling and list a number of informal aspects of this methodology. The main attention is focused on the phenomenon of the existence of multiple models of the same cognitive situation, and on interactions between the subject and the object of the model. A number of examples illustrating our methodology is analyzed.
  Keywords: mathematical models, experiments, model subject

Part 2. Special questions of Intelligent systems theory

• Д.В. Алексеев. Кодирование изображений, инвариантное относительно проективных преобразований (in Russian).
  
  A method of image encoding invariant with respect to projective transformations is presented. It is shown that under some additional requirements code equivalence is equivalent to projective equivalence of images.
  Keywords: projective transformation, image encoding
• Д.Н. Жук. Континуальность множества предполных классов в классе дефинитных автоматов (in Russian).
  
  Definite automata are all finite automata that can be obtained from boolean functions and delay unit using operations of superposition. In this paper cardinality of the set of all precomplete classes for definite automata is proved to be continuum.
  Keywords: definite automata, continuum, precomplete class, cardinality
• С.Д. Махортов. Основанный на решетках подход к исследованию и оптимизации множества правил условной системы переписывания термов (in Russian).
  
  The article is devoted to an approach studying and optimization of sets of rules for conditional term rewriting systems. The approach is based on lattices.
  Keywords: predicate, term
• И.Н. Молодцов. Математическое моделирование упругопластических процессов с траекториями средней кривизны (in Russian).
  
  We obtained and studied four-term differential equations for tension and deformation in plastically deformed materials under complex loading. We also proposed a variant of the determining functions identification and compared it with the mean curvature theory.
  Keywords: mathematical modelling, differential equations
• Т.А. Ракчеева. Квазилемнискаты в задаче приближения формы кривых (in Russian).
  
  We proposed and developed a method of focal approximation of smooth closed curves. The method is based on the family of multifocal lemniscates parametrized by a radius and a finite set of focuses inside the curve. An analysis of a more general family of quasi-lemniscates singles out the family of lemniscates as fulfilling more general requirements to the distance function and the description of geometrical forms and their invariants.
  Keywords: curves, focuses, lemniscate, ellipse, form, transformations, invariant, basis, metrics, approximation, degree of freedom, form generation, interactive control
• Е.А. Снегова. Случай задачи об опасной близости, сводящийся к одномерному интервальному поиску (in Russian).
  
  This paper deals with a special case of dangerous nearness task. The reduction of this case to the one-dimensional interval search task is proved
  Keywords: interval search, one-dimensional interval search
• А.П. Соколов. Асимптотика логарифма сложности перестройки нейронов (in Russian).
  
  Threshold functions defined by linear forms x₁w₁ + ... + x_nw_n – s with integer coefficients are examined. Complexity of transferring one threshold function specified by the linear form into another is examined. Changing of a weight coefficient of threshold by one is a measure of complexity of learning. This process models learning of neuron with threshold activation functions. The asymptotics of a logarithm of a learning time is found when number of variables n grows to infinity.
  Keywords: threshold functions, learning complexity of neurons
• Б. Стаматович. Автоматное распознавание трехсвязных лабиринтов с конечным циклическим диаметром (in Russian).
  
  Pattern recognition is a popular area in computer science. Character recognition is the special case of pattern recognition. The idea of using chess labyrinthes is applicable to the raster images representation. The class of labyrinthes C8 is defined, which represents the digit '8' (in geometric sence). It is proved in the paper [1] that a recognizing automaton for this labyrinth class doesn't exist. It is shown in the paper [2] that a recognizing collective of automata of the type (1,1) for the labyrinth class C8 exists. Here the task for the labyrinth subclass C8d with a finite hole diamater is solved
  Keywords: labyrinth, triply connected labyrinth, automaton, finite automaton, automate recognition
• Д. Цымжитов. Об одном алгоритме ML-декодирования для низкоплотностных кодов (in Russian).
  
  In the article a soft decoding algorithm for low density binary codes with Tanner graphs without cycles is proposed. It is shown that this algorithm provides an optimal solution of decoding problem using maximum likelihood and has asymptotic complexity of O(n) where n is codeword length
  Keywords: code, low density code, decoding, binary code

Part 3. Mathematical models

• Г.В. Боков. Проблема полноты в исчислении высказываний (in Russian).
  
  In this work the problem of axiomatic system completeness is regarded from the point of closure operator generated by the given inference rules. Some properties of the above-mentioned operator are described as well as some properties of closed and precompleted classes set by this operator. Algorithmically unsolvability of completeness problem for finite axiomatic system in propositional calculus is proved.
  Keywords: completeness, proposition, propositional calculus, axiom, inference rule
• Н.Ю. Волков. О возможности поимки жертв в квадранте (in Russian).
  
  The process of pursuit of several independent "victim" automata by a collection of "predator" automata is studied. Pursuit is performed in a quadrant maze. We show that there exists a finite collection of "predators" that "catches" an arbitrary finite independent set of "victims" with fixed speed and view, for arbitrary starting points of "victims" and arbitrary starting point of "predators" (all predators start from the same position).
  Keywords: pursuit, maze, collection of automata, simulation, universal Turing machine, automata calculations
• Ю.И. Вторушин. О поиске вывода в системе натуральной дедукции логики предикатов (in Russian).
  
  In the article the method of the automatic proof of theorems, which is used in systems of deduction automation named Class and Int, is described. The published algorithm finds derivations within the framework of multisortable system of natural deduction which sufficiently models real human reasoning. The algorithm is full for minimal, intuitionistic and classical systems of natural deduction of predicate logic.
  Keywords: predicate, predicate logic, deduction, natural deduction
• А.В. Галатенко, В.В. Галатенко. О расстоянии Хэмминга между почти всеми функциями алгебры логики (in Russian).
  
  A precise estimation of Hamming distance between almost all Boolean functions is presented
  Keywords: Hamming distance, Boolean function
• Ю.Г. Гераськина. О переводимости состояний автоматной модели легких в чистой среде (in Russian).
  
  In the work an automaton model of the process of substance transportation in lung structures in clean environment is offered. The process of lungs clearance during their vital activity is considered. For a proposed automaton model the following problems are being decided – determination of medium depth of a Moore diagram, determination of the criterion of a transition of some state into another state and evaluation of time of such a transition.
  Keywords: automaton, Moore diagram, lung structures, process of substance transportation, transition of automation states, bronchi
• Д.Н. Жук. Разрешимые случаи задачи об A-полноте для дефинитных автоматов (in Russian).
  
  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 A-completeness problem for these sets of definite automata is solvable were found.
  Keywords: definite automata, completeness problem, solvability
• М.А. Кибкало. О сложности представления коллекции языков в конечных автоматах (in Russian).
  
  The problem of language complexity is one of traditional tasks of the finite automata theory. In this paper, we consider automata accepting collections of finite languages. There are different definitions of finite language complexity based on features of the language and the accepting automaton. We understand complexity of a finite language (a collection of finite languages) as the number of states in the reduced finite automaton accepting this language (collection). We found exact values of maximal complexity depending on the maximal word length in the language (collection)
  Keywords: maximal complexity, automaton, automata, finite automata, reduced automata, boolean language, boolean function, Shannon function
• Н.С. Кучеренко. О промежуточных функциях роста сложности поиска для случайных баз данных (in Russian).
  
  In the work complexity of optimum algorithms for key search on the average on a classes of problems are considered. Growth functions of such complexity are studied. Earlier the author investigated cases when growth function was limited function or has the order of logarithm from database capacity. In given article the author investigated growth functions which are nonbounded functions, but under the order smaller, than the logarithm from database capacity. Family S of possible asymptotics and family S* of possible orders of such growth functions are described.
  Keywords: search, complexity, database, search algorithm
• А.А. Летуновский. О выразимости константных автоматов суперпозициями (in Russian).
  
  The expressibility problem for finite automaton by system Ф U nu is considered. Ф consists of all k-valued functions and "delay" function. nu is a finite automata system. Previously author has shown the existence of algorithm for checking expressibility of automaton A by {Ф U nu}, where A is automaton with unconditional transitions. Author solve the problem of expressibility of automaton A by {Ф U nu}, where A is automaton with soluble group.
  Keywords: expressibility, finite automaton, delay function, constant automaton, algorithm existence, soluble group
• И.В. Лялин. Решение автоматных уравнений с двумя неизвестными (in Russian).
  
  Let S is a digital circuit, which is consisted from finite-state machines. Let some finite-state machines x₁, ..., x_N are possible to be changed to other finite-state machines x'₁, ..., x'_N with the same input and output alphabets. Are there exist such x'₁, ..., x'_N that after substitution x₁, ..., x_N -> x'₁, ..., x'_N, S will be equivalent to the finite-state machine h? The article proves that there are no algorithm for solving this problema if N >= 2.
  Keywords: finite-state machine, FSM, digital circuit, FSM equation, algorithmically unsolvable problem
• М.В. Носов. Комбинаторная формула числа пороговых функций (in Russian).
  
  In this paper a conclusion of the combinatory formula setting number of threshold functions is presented. To derive the formula a conclusion Lagrange polynomial is used. The top estimation for length of an edge of the cube which integer points set all threshold functions is used
  Keywords: threshold functions, Lagrange polynomial
• В.В. Осокин. О параллельной расшифровке разбиений булевого куба (in Russian).
  
  In the current paper we consider class Ф^k,n of discrete functions defined over Boolean cube {0,1}ⁿ with no more than k <= n relevant variables. Each function f in Ф^k,n defines a splitting of cube {0,1}ⁿ into nonoverlapping cube faces and assigns a unique number to each cube face of the resulting splitting. We prove the lower bound of learning functions in Ф^k,n complexity and develop an algorithm of learning functions in Фⁿ = Ф^n,n that is optimal in the sense that the number of membership queries that the algorithm needs to learn an arbitrary function in Ф^k,n on the order coincides with the lower bound. The algorithm can be effectively parallelized and when maximally parallelized its complexity equals k on the order.
  Keywords: learning complexity, Boolean cube splitting, attribute-efficient learning, learning juntas, parallel learning, pseudo-boolean functions, exact learning model
• Е.А. Поцелуевская. Теоретическая и практическая сложность задачи о выполнимости булевых формул (in Russian).
  
  In the current work different variants of satisfiability problem statement are described, moreover a review of the most well-known algorithms for its decision, algorithms classification and some theoretical estimations for complexity are shown. At the final part of the article the most notable results obtained in this field during the last 10 years and several practical complexity estimations are regarded.
  Keywords: satisfiability, SAT, review, algorithm, complexity
• А.П. Соколов. Об одном семействе нейронов с ограниченной сложностью взаимной перестройки (in Russian).
  
  Complexity of transferring one threshold function specified by the linear form into another is examined. Changing of a weight coefficient of threshold by one is a measure of complexity of learning. This process models learning of neuron with threshold activation functions. It's described such class of neurons that the complexity of learning one neuron into another within this class is limited by an arbitrary value between 3..n and 3...2ⁿ, where n is a number of variables. At the same time the size of this class grows exponentially with n.
  Keywords: threshold functions, learning complexity of neurons
• Ю.С. Шуткин. Реализация монотонных булевых функций монотонными информационными графами (in Russian).
  
  A problem of monotone Boolean function representation using monotone information graphs is considered. Monotone information graphs have monotone base set, i. e. base set consisting of variables without negations. Complexity estimations for different subclasses of this problem were obtained
  Keywords: boolean function, monotone boolean function, information graphs, boolean functions representation