Русский язык
Volume 14, issue 1-4, 2010
Part 1. General problems of the theory of intelligent systems
- Baranovich A.E.. On the systematization of the axiomatic apparatus of the subject area "Artificial Intelligence".
With the positions of the information-evolutionary approach, questions of systematization of the axiomatic foundation of a object domain of the science, called now by "artificial intelligence" (AI), are considered. In contexts of scientific and ordinary consciousness it is a question what to eat ``naturally'', and that is ``unnaturally'' and is ``artificially'' in AI. Results of the lead analysis allow to make essential changes to phenomenology of its development.
Keywords: "Big history"; informatization; information-evolutionary approach; intelligence natural, artificial; intelligence computing, computer, technical; modelling; systems anthropogenous, anthropomorphous, intelligent, material
Part 2. Special issues of the theory of intelligent systems
- Kozlov V.N.. Evidence and heuristics in visual image recognition.
In article are described in the short form the basic ideas as a principle of the is discrete-geometrical approach to recognition of visions, and at descriptive level the received results are described. Some reasons about the role of heuristics in recognition of visual images are discussed.
Keywords: recognition of images, visions, 3D-reconstruction of images - Masloboev A.V., Lomov P.A.. Using a system-wide thesaurus as the basis for an intelligent user interface of a distributed semantic search system.
This paper considers the application problem of expanded systems-wide thesaurus as the basis of intellectual interface of the distributed semantic retrieval information systems. The definition of shared thesaurus expansion by units of the top-level ontology and meta-properties is proposed. The inquiry formation technology based on identification procedures of its meshing possible variants that allows the thesaurus application as the basis for intellectual user interface design has been developed.
Keywords: information system, ontology, thesaurus, semantic information integration, query manipulation, intelligent user interface - Adylova L.R.. On face recognition.
Methods of geometrical recognition of race of the person on a photo are studied. Geometrical invariants of face, allowing to refer it to one of three racial clusters: mongoloid, caucasian, negroid are found. Was found 11 such invariants in the form of points of the face at definitely set system of coordinates. On these points the code was constructed and then various methods of recognition of persons were applied to it.
Keywords: recognition, invariants, geometrical methods, race, training - Bokov G.V.. Pontryagin's maximum principle in a problem with time delay.
In this paper we consider a certain optimal control problem with time-delay. The state and the control variables contain various constant time-delays. It allows us to represent the necessary conditions in an explicit form. Solution of this problem with infinite terminal time is also given.
Keywords: Optimal control theory, time-delay differential equations, necessary conditions, maximum principle, finite and infinite terminal time - Gazaryan V.A. Matveeva T.V. Chekhonina Yu.G. Shakhovskaya A.K.. On the theoretical-possibility methods of analyzing the effectiveness of treatment.
[1] shows that for solving many problems in medical diagnostics possibilistic model of data analysis and interpretation [2] is natural instead of probabilistic one. The possibilistic model of disease symptoms and possibilistic model of medical diagnosis were built. The aim of this work is developing of possibilistic methods for analyzing the effectiveness of treating of chronic pancreatitis patients. Particularly is developing of effect produced by one or another drug on the state and on biochemical indices of blood of such patients estimating method.
Keywords: theory of possibility, testing of statistical hypotheses, t-test, effectiveness of treating, chronic pancreatitis - Galatenko A.V.. On restoring security partitioning.
We consider an automaton system; a subset of states of the automaton is considered to be secure. We investigate the complexity of reconstruction of such security partitions for secure and epsion-secure languages introduced in the article ``Automata models of secure computer systems''.
Keywords: Finite automaton, automata models, multiple conditional experiment - Gasanov E.E., Kolesnichenko A.V.. Predicate equivalence of Boolean formulas.
Predicate equivalence of Boolean algebra formulas is investigated in the paper. Predicate equivalence is defined with help of a set of predicates P and a set of permutations M. The sets P and M are conformed if predicate equivalence coincides with common equivalence of Boolean formulas. Criterion of the sets conformity is proved. The algorithm of construction of conformed sets is suggested. Examples of conformed sets P and M are given.
Keywords: Boolean algebra, predicate logic, analytic description of geometric figures - Dokuchaeva T.V.. The process of self-cleaning of the lungs with focal lesions in a clean environment.
In this paper we have constructed the model of functioning of lungs with pathologies. We have considered the function of lungs self-cleaning from the substance that gets into them from environment or is being produced in it during life. We have expanded the mechanism of substance transportation in healthy lungs to a case of pathologies of capacity and efficiency of ciliary mechanism. We have received the description of lungs self-cleaning process time complexity with pulmonary pathologies of ciliary capacity and(or) their efficiency in clean environment.
Keywords: bioinformatics, dendritic systems, lungs, ciliary mechanism, self-cleaning, transportation process - Kolesnikova S.I.. Properties of correct modification of the paired comparison method.
Properties of function of relative similarity as scalar measure of convolution of criteria used according to the method of paired comparisons are considered. Application of the function of relative similarity allows to correction of unwanted effects of known Т. Saaty’s method. Effects are related to using of linear convolution of criteria and of unit normalization of weight coefficient of alternatives. The illustrative example is given.
Keywords: method of analytical hierarchies, alternative weight coefficients, intelligence system, test pattern recognition, quality of decision-making - Levin V.Yu.. On increasing the cryptographic resistance of one-way hash functions.
In this paper we introduce a solution of a data integrity ensuring using cryptographic one-way hash functions. The cryptographical security of such hash-functions was estimated by us in detail for different kinds of attacks. We propose a several new schemes of a one-way hash functions security strengthening without reformation of it’s internal algorithms. Also we outline schemes with the best speed and security level. We show that the Schneier’s method of suffix superposition has seriously drawback. In this article we also suggest the method of constructing collision resistant one-way hash-functions from standard well-known hash-functions. Therefore, the proposed schemas can be used for upgrade majority cryptographic one-way functions, such as MD4, MD5, RIPEMD, SHA, GOST 34 11-94.
Keywords: one-way hash-functions, Schneier’s method, message integrity, tunnel collisions, information security - Parkhomenko D.V.. Modeling by probabilistic sources.
Hidden Markov Model (HMM) – this is Markov chain, which has user-visible "exit". In accordance with state-dependent distribution law, in the every state HMM provides an output character and moves to the next state. If output alphabet is finite, HMM is called probabilistic generator. The article describes usage of HMM-based devices and gives an account of the actual engineering problems, where they are used.
Keywords: hidden Markov models, image recognition, probabilistic generator - Petyushko A.A.. On Markov random fields and their connection with Markov chains.
This work is about markov random field and hidden markov random field. Some relationships are established between markov random fields and markov chains, and between hidden markov random fields and hidden markov models using the special introduced random variables.
Keywords: Markov random field, mrf, hidden Markov random field, hmrf, markov chain, hidden markov model, hmm - Pivovarov A.P.. Modeling of computational problems of information retrieval.
This paper contains definitions and comparison of two models for computational information search problems algorithms description. First of them almost identical to the information graph model. The second uses automata functions for calculations. The answer cardinality search for one-dimensional interval search problem is used as a model problem for this study. The advantages of automata functions usage in computational information search problems are shown.
Keywords: computational information search problem, information graph, computational information graph, one-dimensional range searching, search modelling, search algorithms characteristics - Rykov D.O.. On algorithms for checking the correctness of families of functions.
This paper considers the problem of propriety checking for families of functions. A new algorithm of propriety checking is introduced. The algorithm uses information about the graph of the family of functions and the complexity of the algorithm depends on the number of vertices in strong components of the graph. A new algorithm for families of monotonous functions is also introduced. The algorithm is based on two properties of proper families of monotonous functions: the presence of constant and functional closure of that class in $P_2$. It is demonstrated that the complexity of the algorithm is considerably less than complexity of the standard propriety checking algorithms.
Keywords: Proper family of functions, propriety checking algorithm for families of functions, graph of essential dependence of family of functions, family of monotonous functions, propriety criterion for family of functions.
Part 3. Mathematical models
- Blokhina G.N., Kudryavtsev V.V.. On spectra of Post classes of Boolean functions.
- Bolonkin M.V.. On virus recognition in regular texts.
In this paper we study properties of regular expressions and identical transformations of regular expressions on the issue of modelling of polymorphic viruses. Model of infection, weak and strong infection of program with virus is defined. The main contribution of this work is to find criteria of infection with virus and start modelling programs and virus properties in terms of regular expressions. As has been proved, there exists a criterion for infection (weak or strong) of *-free programs and criteria for some classes of regular expression with Kleene star.
Keywords: recognition, viruses, regular expression, subexpressions - Kibkalo M.A.. On the automaton complexity of some classes of Boolean functions.
We investigate the question of asymptotic behavior of maximal state complexity of a language represented by a DFA. We determine that closed sets of Boolean functions from Post's lattice divide into three groups in correspondence with their asymptotic complexity. Moreover, for certain sets exact values of maximal complexity are produced.
Keywords: complexity, DFA, finite automata, finite automaton, Boolean function, Shennon function, Post's lattice - Kucherenko N.S.. The problem of searching by key with determination of position.
Two ways of formalization of key search are studied in the article. They are the identical objects search (IOS) and expanded IOS. It is shown, that the search complexity for these ways of formalization are identical. The algorithm of transformation is described, which transforms solution for IOS to solution for expanded IOS without change of complexity.
Keywords: database, key search, search algorithm - Lasheva M.I.. On switching algorithms for transforming some classes of graphs.
In this paper we consider so called edge-switching algorithm created the transformation procedure for any pair of some class graphs keeping the same degree sequence and the particular class. The algorithm under consideration can be of use for the network optimization problem with the given set of providers and its communication capability. Due to its properties the algorithms of that kind don't require researching the global features of the network, only the local one.
Keywords: degree sequence, finite state automaton, edge-switching algorithm, trees, unicyclic graphs, connected graphs - Letunovsky A.A.. On expressibility by superpositions of automata with solvable groups.
The expressibility problem for finite automaton by system Phi U nu is considered. Phi consists of all k-valued functions and "delay" function. nu – a finite automata system. Previously author has shown the existence of algorithm for checking expressibility of automaton A by Phi U nu, where A is automaton with unconditional transitions. Author solve the problem of expressibility of automaton A by Phi U nu, where A is automaton with soluble group.
Keywords: expressibility, finite automaton, "delay" function, constant automaton, algorithm existence, soluble group - Li V.A.. Order of complexity of laying trees on a plane.
This paper considers the problem of trees layout on the two-dimensional rectangular lattice. Such layout characteristics as area and edges length sum are minimized. For certain cases there are offered algorithms which are asymptotically optimal by order in both senses.
Keywords: tree layout, rectangular lattice layout, layout length, layout area, minimal layout, layout algorithm - Muravyeva A.A.. On coding discrete figures by segments.
The article deals with the coding of discrete figures by the ordered set of all pairwise distances between their points (spectrum). Some properties of the spectra are considered. An algorithm for constructing all the figures with a given spectrum in the space of any dimension is presented.
Keywords: pattern recognition, discrete geometry - Osokin V.V.. On parallel parameter-efficient decoding of pseudo-Boolean functions.
We consider the problem of parallel attribute-efficient learning pseudo-boolean functions in the context of exact learning model. We develop an algorithm of attribute-efficient learning the class of interval-constant functions that is optimal on the order. The class contains in particular the class of pseudo-boolean monotone functions and the class of splitting functions. For some subclasses of interval-constant functions we develop an algorithm of attribute-efficient learning that has both optimal parallel complexity and optimal standard complexity on this subclasses.
Keywords: learning complexity, attribute-efficient learning, learning juntas, parallel learning, pseudo-boolean functions, interval-constant functions, monotone functions, exact learning model - Potseluyevskaya E.A.. A public-key cryptosystem based on the problem of F-satisfiability of Boolean formulas.
In the modern world the considerable part of information is processed in electronic form. The necessity of protection of this information during its transmission over open communication channels has lead to a wide spread of public-key cryptographic systems based on different NP-complete problems. In this article the realization of an asymmetric cryptosystem based on the NP-complete S-satisfiability problem is concerned.
Keywords: cryptographic system, encryption, satisfiability, boolean functions - Potseluyevskaya E.A.. Algorithms for solving the F-satisfiability problem by approximation to Schaefer classes.
In his work "The complexity of satisfiability problems" Thomas J. Schaefer defined 6 boolean functions classes for which the generalized satisfiability problem (so-called S-satisfiability) is decided in a polynomial time. The discovery of the other classes of functions for which the problem could also be solved fast has a significant practical value. In the current work two algorithms for S-satisfiability problem decision are described. These algorithms are based on the boolean functions approximation to the Schaefer classes and under specified constraints for initial functions have polynomial complexity.
Keywords: algorithm, S-satisfiability, Schaefer classes, complexity - Rodin S.B.. Linearly realizable transition systems.
The main purpose of the article is the investigation of "`linear realized"' semiautomata, i.e. semiautomata, which has the state encoding such as the boolean operator inspired by this state encoding is linear. The necessary criterion of linear realizing property is formulated in the article. Also the lower and upper bound estimation of linear realized semiautomata number are formulated.
Keywords: automata theory, semiautomata, transition systems, assignment, state encoding, complexity - Sokolov A.P.. On the complexity of mutual learning of almost all neurons.
Problems of neurons learning complexity are considered in this paper. Threshold functions act as mathemetical model of neurons. Following problem is being studied: what is the complexity of mutual learning of pairs of threshold functions in most cases. Threshold functions are defined by means of linear forms with integer coefficients. Change of any coefficient of the linear form by one is the measure of complexity of mutual learning of threshold functions. It was shown that for quite all pairs of threshold functions the complexity of mutual learning one function into another grows exponentially with growth of number of variables.
Keywords: threshold functions, learning complexity of neural networks - Sokolov A.P.. On one variety of threshold functions.
This paper is devoted to complexity of defining boolean threshold functions by means of linear forms with integer coefficients and absolute term. A very simple example of threshold function with exponential coefficients is presented. For an arbitrary number of variables the corresponding threshold function and integer linear form are explicitly constructed.
Keywords: threshold functions, learning complexity of neural networks - Sokolov A.P.. On constructive characterization of threshold functions invariant with respect to permutation groups.
Classes of boolean threshold functions that are invariant by groups of permutations are considered in the paper. Complete description of these classes is obtained. This description is made in terms of groups of permutations which preserve partitions of varibles. It is shown that quite all threshold functions are nonsymmetric, i.e. they are invariant by only identical permutation. Complexity of defining threshold functions by means of linear forms with integer coefficients is also studied. Term <
> is introduced. Lower and upper bounds of the amplitude were found for the threshold functions invariant by groups of permutations. The complexity of mutual learning one threshold function into another by means of changing the coefficients is also studied. Lower and upper bounds of complexity were obtained for the threshold functions invariant by groups of permutations.
Keywords: threshold functions, learning complexity of neural networks- Tsymzhitov D.. On soft decoding of linear codes by the method of minimal words. In this paper we consider the modification of well-known minimal-codewords decoding algorithm, having an explicit limitation on the maximum number of iterations in the form of some constant t. If the allotted number of iterations is not enough to obtain optimal solution, the algorithm declares failure. We suggest a lower bound for the constant t, compliance with which ensures that the probability of decoding failure will be close to zero. If n is the length of the codeword, then this bound is O(ln(n)) when n -> inf. This new bound is an improvement of formerly known linear bound.
Keywords: soft-decision decoding, maximum-likelihood decoding, gradient-like decoding, linear block codes, minimal codewords, minimal vectors, decoding complexity- Chernova Yu.G.. On the states of condensation of the automaton model of the lungs in a clean environment. In the article an automaton model of lungs selfcleaning process is offered and the exploration of properties of its Moore diagram continues. The special class of states of this diagram, namely the states which have the largest number of predecessors in clean environment are allocated. In the article there is criterion description of such states, their number are given, as well as the number of direct predecessors of each state of condensation is found.
Keywords: automaton, Moore diagram, lungs, the process of selfcleaning, state of condensation- Chlenova T.S.. On the layering of Boolean functions and functions of k-valued logic. The article introduces a lamination of complete systems in Pk, k >= 2. The upper estimate of the lamination of an arbitrary complete system in P2 is obtained. In the case of Pk, k >= 3, the problem of complete systems lamination finiteness is reduced to the problem of Slupecky systems lamination finiteness. A quite wide class of Slupecky systems with the finite lamination is also demonstrated.
Keywords: boolean function, function of k-valued logic, complete system, complexity, lamination- Shutkin Yu.S.. On the simultaneous minimization of the volumetric and time complexity of contact and valve circuits. Parallel optimization of contact circuits size and time complexity is investigated. With size of contact circuit or oriented contact circuit we mean the number of contact elements in the circuit. With time complexity of the circuit we mean the average time which model algorithm spend for calculation of the Boolean function value. The model of the circuit is defined directly by circuit structure and formalized in terms of information graphs. A method of contact and oriented contact circuits synthesis which is asymptotically optimal for both size and time complexity is proposed.
Keywords: Contact circuits, information graphs, contact circuits time complexity- Sokolov A.P.. Letter to the editor.
- Tsymzhitov D.. On soft decoding of linear codes by the method of minimal words. In this paper we consider the modification of well-known minimal-codewords decoding algorithm, having an explicit limitation on the maximum number of iterations in the form of some constant t. If the allotted number of iterations is not enough to obtain optimal solution, the algorithm declares failure. We suggest a lower bound for the constant t, compliance with which ensures that the probability of decoding failure will be close to zero. If n is the length of the codeword, then this bound is O(ln(n)) when n -> inf. This new bound is an improvement of formerly known linear bound.