Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N7 2016 year

DOI: 10.17587/prin.7.330-336
About Implementation of Approximation the Number of Layers without Cycles in the Fuzzy LP-Inference Problem
A. N. Shmarin, e-mail: tim-shr@mail.ru, Voronezh State University, Voronezh, 394006, Russian Federation
Corresponding author: Shmarin Artem N., Postgraduate Student, Voronezh State University, Voronezh, 394006, Russian Federation, e-mail: tim-shr@mail.ru
Received on April 08, 2016
Accepted on April 19, 2016

The increase in the volumes and complexity of processed information makes the use of artificial intelligence systems more and more actual. In such systems, one of the most widespread knowledge representation models is the production model and search algorithms are based on the inference engine. In practice, obtaining information about the subject area status is time-consuming operation for many problems. The examples are the requests to the DBMS, the analysis of medical data or other complex sequences of calculations can be those. Often in such problems, the search for solution (or set of possible solutions) is performed in the absence of part of information about the subject area status. This circumstance requires optimal use of limited resources. There are tasks of control of complex objects with random processes (risk management, socio-economic systems), in which the control process is based on fuzzy knowledge representation model. For them, the result of the controlling influence can be predicted only with some probability. In addition, process of obtaining information that is necessary for making decision about the control action can be time-consuming operation. In such situations it is necessary to maintain or to bring the system to the predetermined state, spending as little as possible resources for time-consuming operations of obtaining the necessary information, taking into account at the same time the fuzziness of the relationship between knowledge. The complexity of the operations of data acquisition necessary for decision-making, leads to the problem of minimizing the number of requests for information about the subject area status during inference. This problem is NP-hard. To achieve global minimization there is the general method of LP-inference with exponential computational complexity relative to the number of atomic facts in the knowledge base. However, some of its heuristic modifications have polynomial complexity. The goal of the provided research is development of the approximating method to better minimize the number of requests performed in the inference. Earlier, the structural properties of partition of the binary relation were considered, based on which it is possible to select for the analysis such subset of production, that most significantly changes the rate of relevancy. This paper presents the method for calculating the value of the exact number of layers without cycles based on capacities of quotient set equivalence classes that builds as the partition of binary relations by unique right parts. In addition, this paper considers questions of the algorithmic implementation of components that are necessary to calculate the approximate value of the number of layers without cycles. The presented approach can be applied to accelerate the reverse inference in production type systems of artificial intelligence. It can be extended also to more complex logical systems in computer science.

Keywords: LP-inference, quotient set, binary relation, cycle basis, NP-hardness, algorithms, python
pp. 330–336
For citation:
Shmarin A. N. About Implementation of Approximation the Number of Layers without Cycles in the Fuzzy LP-Inference Problem, Programmnaya Ingeneria, 2016, vol. 7, no. 7, pp. 330—336.
This work was supported by the Russian Foundation for Basic Research, project nos. 15-07-05341