Contents of magazine "Intelligent systems"
Volume 12, issue 1-4, 2008
Part 1. General problens of Intelligent systems theory
Part 2. Special questions of Intelligent systems theory
Part 3. Mathematical models
- Д.Н. Бабин, А.Б. Холоденко. Об автоматной аппроксимации естественных языков (in Russian).
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
- Н.Ю. Волков. Об автоматной модели преследования внутри квадрата (in Russian).
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
- Б.В. Воронин, В.В. Осокин. О сложности расшифровки существенных переменных функции, задающей разбиение булевого куба (in Russian).
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*log2n 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: log2n and n correspondingly
Keywords: variable learning complexity, Boolean cube splitting, attribute-efficient learning, learning juntas, pseudo-boolean functions, exact learning model
- Ю. Г. Гераськина. Автоматная модель транспортировки вещества по легким в загрязненных средах (in Russian).
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
- Д.Н. Жук. О неразрешимости проблемы полноты для дефинитных автоматов (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 the completeness and A-completeness problem for these sets of definite automata is unsolvable were found.
Keywords: definite automata, completeness problem, unsolvability
- Д.В. Зайцев. О сложности вложения матриц (in Russian).
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
- В.Ю. Лёвин, В.А. Носов. Анализ повышения криптографической сложности систем при переходе на эллиптические кривые (in Russian).
Keywords:
- И.В. Лялин. Решение автоматных уравнений с одной неизвестной (in Russian).
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
- С.В. Моисеев. О реализации автоматов нейронными сетями (in Russian).
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
- В.А. Носов, А. Е. Панкратьев. О функциональном задании латинских квадратов (in Russian).
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
- А.П. Пивоваров. Поиск представителя в задаче о метрической близости (in Russian).
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
- Е.А. Поцелуевкая. Полиномиальные случаи решения задачи об F-выполнимости булевых формул. (in Russian).
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 xi 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
- А.П. Соколов. О конструктивной характеризации пороговых функций (in Russian).
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
|
