Volume 15, issue 1-4, 2011

Part 1. General Problems of the Theory of Intelligent Systems

• Editorial staff of the journal "Intellectual Systems". Valery Borisovich Kudryavtsev. On the 75th Anniversary of His Birth.
• Baranovich A.E.. Information-Evolutionary Approach in the Theory of Intelligent Systems. The projection of the information-evolutionary approach to the system analysis and modeling of an objective reality on a problem domain of the theory of intelligent systems is investigated. The offered phenomenology of the theory allows to evaluate the used apparatus of modeling of complex dynamic systems from constructive positions and to specify the basic directions in research of universal mechanisms of intellectual activity.
  Keywords: intelligence modeling, models of evolution of an objective reality, modeling of complex systems, systems genesis, theory of intelligent systems, universal mechanisms of thinking
• Shcherbina O.A.. Constraint Satisfaction and Constraint Programming. A review of the main directions of constraint satisfaction (CS) and constraint programming is presented. The purpose of the CS problem (CSP) is finding the values of the variables satisfying certain restrictions. In artificial intelligence the CSP paradigm is recognized as a convenient and effective method of modeling and solving many applied combinatorial problems. The important task of answering the conjunctive queries in the database theory can be considered as a CSP. Moreover, CSPs attract great attention in the complexity theory as various versions of CSPs are in the middle of many standard complexity classes and they have a tendency not to have the intermediate complexity, that is they are either easily solvable or complete for the standard complexity classes. Constraint programming is a programming paradigm for the declarative description and effective solving of combinatorial problems, tightly connected to CSP theory. Examples of CS models usage and applications are considered.
  Keywords: constraint satisfaction; constraint programming; complexity; combinatorial problems

Part 2. Special issues of the theory of intelligent systems

• Ashirmatov B.D.. Multidimensional search in learning systems. In this paper we study the multidimensional nearest neighbor problem in database on specific data model. We introduce a data model, study its properties. The model is generalized to the continuous case, also its features are investigated. Based on models features a search algorithm in database was proposed and implemented.
  Keywords: multidimensional search, learning systems, teaching systems, data model, search algorithm, nearest neighbor problem, database, properties, modeling, space partition
• Parkhomenko D.V.. Method of recognizing a set of words through the synthesis of a deterministic automaton. This paper proposes a recognition method by constructing a finite state automaton recognizing the set of its output words. Properties of multisets, emerging at the output of deterministic automata, are investigated. Estimations of the complexity of the algorithm for constructing an automaton from the multiset are given.
  Keywords: finite state automaton, finite state machine, image recognition, output set of the automaton, image recognition through the FSM synthesis
• Pivovarov A.P.. Partial cascading technique for iterative search in linearly ordered sets. Iterative search is a search of one key in multiple linearly ordered lists. Fractional cascading technique can be used to avoid proceeding separate binary searches for all iterations. Amount of required space can be multiplied by at most constant factor. Time required for every iteration except first can be bounded depending on iterative search branching parameters. This paper describes fractional cascading technique and estimates size of obtained data structures.
  Keywords: fractional cascading, iterative search, space-time tradeoff
• Potseluyevskaya E.A.. On some properties of Schaefer classes. The issue of sizes and properties of Schaefer's classes has been being comprehensively examined since Schaefer had described these classes. In particular, a significant contribution to research of this question was introduced by works of the authors Alekseev V.B., Gorshkov S.P., Gizunov S.A., Nosov V.A. and Tarasov A.V. Some particular properties of Schaefer's classes, that could be useful to solve of the S-satisfiability problem fast or, alternatively, to form difficult for solution tasks, are considered in the article.
  Keywords: Schaefer's classes, S-satisfiability, precompleteness, algorithm
• Snegova E.A.. A criterion for the reducibility of the problem of dangerous proximity to the puncture problem. Consider two streams of moving objects inside the square [0, 1]². One of the streams moves from South to North and we call it a stream of queries, and another stream moves from West to East and we call it a stream of objects. Moving objects closeness problem (MOC problem) consists of enumeration for every new query those and only those objects that will be not far than . from the query in Manhattan metrics at some moment of time during the query's or the objects' movements inside the square. In this paper we present and prove criteria for reducibility of the MOC problem to one-dimensional stabbing problem.
  Keywords: databases of moving objects, spatio-temporal databases, information graph, complexity
• Chuchalin A.G., Kudryavtsev V.B., Alekseev D.V., Anaev E.Kh., Anokhina T.N., Nosov M.V., Revelsky A.I., Revelsky I.A., Rodionov A.A.. Mathematical and computer processing of KVV experiments on recognition of pulmonary diseases. The article is devoted to research of methods diagnosis of COPD and asthma based on study of semi-volatile organic compounds (SvOC) on ultra-low level in exhaled breath condensate (EBC) with use of methods of admixture detection and chromatography-mass spectrometry of EBC. There were collected 70 EBC samples from patients with acute exacerbations of obstructive lung diseases (20 – with asthma, 20 – with COPD) and 30 healthy nonsmokers using an ECoScreen condenser. Testing for SvOC with different polarity in EBC was conducted by gas chromatography/mass-spectrometry (GC/MS) method. The collected data were analyzed using an algorithm based on linear methods of pattern recognition theory. The methods showed that it is possible to distinguish asthma patients from healthy with reliabilty equal to 75%, COPD patients from healthy with reliability 85% and COPD patients from asthma patients with reliabilty 83%. Some substances were detected that may can potentially be the markers for those diseases.
  Keywords: pattern recognition, chronic obstructive pulmonary disease, asthma, exhaled breath condensate, chromatography-mass spectrometry

Part 3. Mathematical models

• Agniashvili P.G.. Uniqueness of image restoration from its code in the n-dimensional case. The paper considers discrete-geometrical approach to visual recognition in case of arbitrary finite dimension. Necessary and sufficient conditions are obtained that give a criterion of unique image recovery by its code. A geometrical interpretation is given that describes the class of allowable images. The case of degenerate images is particularly considered.
  Keywords: visual recognition, image code, modified code, image recovery uniqueness
• Galatenko A.V.. On approximation of regular languages ​​by safe languages. We investigate approximation properties of secure languages introduced in the atricle "Automata models of secure computer systems". We consider lower and upper approximations of regular languages and estimate possible values of secure languages growth.
  Keywords: secure languages, regular languages, language approximation, growth functions
• Dergach P.S.. On the unambiguity of alphabetic decoding of regular texts. А.А. Markov reduced the one-to-one problem of the alphabetic decryption of all messages in the fixed alphabet A to the decryption of the finite set of words in this alphabet with length less than some fixed constant. This constant is determined by the encryption scheme, power of the alphabet A and some other quantities [1]. This paper considers the case when encrypted set is regular. It is shown that Markov's result may be generalized to the case of alphabetic decryption of the arbitrary regular set.
  Keywords: one-to-one property of the alphabetic decryption, regular text
• Ivanov I.E.. Some classes of functions computable by automata. In the current paper we consider some classes of functions computable by finite automata, pushdown automata and 2-way pushdown automata.
  Keywords: automata, pushdown automata, computable function
• Kibkalo M.A.. On the automaton complexity of Post classes of Boolean functions. Boolean vectors for which a Boolean function f:{0,1}ⁿ → {0,1} is equal to 1 could be treated as words of the finite language L_f. Let automata complexity of f be the minimal state number of the deterministic finite automaton accepting L_f. The automata complexity of a Boolean function set is the maximal complexity of a function from this set. For a Boolean function class K we define the Shannon function as the automata complexity of the n-variable function set from K. Here we consider the automata complexity of Boolean functions and determine precise values or asymptotic estimations of Shannon functions for all closed Post classes of Boolean functions.
  Keywords: boolean function, deterministic finite automaton, automata complexity, closed Post class, Shannon function
• Letunovsky A.A.. On the problem of expressibility of automata with respect to superposition for systems with fixed additive. We consider the problem of expressibility finite group Medvedev-automaton M using superpositions F U R, where F consists of all Boolean functions and the "delay", R – arbitrary finite system of automata. Earlier, the author showed that for Medvedev-automaton solvable group M, there exists an algorithm to test membership M in [F U R]. In this paper we solve a similar problem of expressibility arbitrary group Medvedev-automata.
  Keywords: automaton, superpositions, Boolean functions, expressibility
• Mastihina A.A.. Partial guessing of super-events generated by simple LL(1)-grammars. A machine predicts an input symbol if this symbol is equal to its output symbol in previous moment. A machine partially predicts a set of w-words if it predicts some substantial part of symbols in any w-word. An algorithm determining wether the set of w-words generated by LL(1) grammar is partially predictable is described.
  Keywords: predicting automata, pushdown automata, partial prediction, w-languages, LL(1) grammars