RU
Volume 13, issue 1-4, 2009
Part 1. General problems of the theory of intelligent systems
- K.E. Plokhotnikov. Mathematical modeling and computational experiment: methodology and practice.
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 issues of the theory of intelligent systems
- D.V. Alekseev. Image coding invariant with respect to projective transformations.
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 - D.N. Zhuk. Continuity of the set of precomplete classes in the class of definite automata.
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 - S.D. Makhortov. A lattice-based approach to the study and optimization of the set of rules of a conditional term rewriting system.
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 - I.N. Molodtsov. Mathematical modeling of elastic-plastic processes with trajectories of average curvature.
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 - T.A. Rakcheeva. Quasilemniscates in the Problem of Approximating the Shape of Curves.
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 - E.A. Snegova. A case of the problem of dangerous proximity, reduced to a one-dimensional interval search.
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 - A.P. Sokolov. Asymptotics of the logarithm of the complexity of neuron reorganization.
Threshold functions defined by linear forms x1w1 + ... + xnwn – 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 - B. Stamatovic. Automatic recognition of three-connected labyrinths with finite cyclic diameter.
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 - D. Tsymzhitov. On one ML-decoding algorithm for low-density codes.
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
- G.V. Bokov. The problem of completeness in propositional calculus.
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 - N. Yu. Volkov. On the possibility of catching victims in the quadrant.
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 - Yu. I. Vtorushin. On the search for a conclusion in the system of natural deduction of predicate logic.
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 - A.V. Galatenko, V.V. Galatenko. On the Hamming distance between almost all functions of Boolean algebra.
A precise estimation of Hamming distance between almost all Boolean functions is presented
Keywords: Hamming distance, Boolean function - Yu. G. Geraskina. On the translatability of states of the automaton model of lungs in a clean environment.
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 - D.N. Zhuk. Solvable cases of the A-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 A-completeness problem for these sets of definite automata is solvable were found.
Keywords: definite automata, completeness problem, solvability - M.A. Kibkalo. On the complexity of representing a collection of languages in finite automata.
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 - N.S. Kucherenko. On intermediate functions of search complexity growth for random databases.
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 - A.A. Letunovsky. On the expressibility of constant automata by superpositions.
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 - I.V. Lyalin. Solving automaton equations with two unknowns.
Let S is a digital circuit, which is consisted from finite-state machines. Let some finite-state machines x1, ..., xN are possible to be changed to other finite-state machines x'1, ..., x'N with the same input and output alphabets. Are there exist such x'1, ..., x'N that after substitution x1, ..., xN -> x'1, ..., 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 - M.V. Nosov. Combinatorial formula for the number of threshold functions.
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 - V.V. Osokin. On parallel decoding of partitions of the Boolean cube.
In the current paper we consider class Фk,n of discrete functions defined over Boolean cube {0,1}n with no more than k <= n relevant variables. Each function f in Фk,n defines a splitting of cube {0,1}n 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,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 - E.A. Potseluevskaya. Theoretical and practical complexity of the problem of satisfiability of Boolean formulas.
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 - A.P. Sokolov. On one family of neurons with limited complexity of mutual reorganization.
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...2n, 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 - Yu.S. Shutkin. Implementation of monotone Boolean functions by monotone information graphs.
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