Mivar NETs and logical inference with the linear complexity

Олег Олегович Варламов

MIVAR: Transition from Productions to Bipartite Graphs MIVAR Nets and Practical Realization of Automated Constructor of Algorithms Handling More than Three Million Production Rules. The theoretical transition from the graphs of production systems to the bipartite graphs of the MIVAR nets is shown. Examples of the implementation of the MIVAR nets in the formalisms of matrixes and graphs are given. The linear computational complexity of algorithms for automated building of objects and rules of the MIVAR nets is theoretically proved. On the basis of the MIVAR nets the UDAV software complex is developed, handling more than 1.17 million objects and more than 3.5 million rules on ordinary computers. The results of experiments that confirm a linear computational complexity of the MIVAR method of information processing are given.

O.O. Varlamov

MIVAR: Transition from Productions to Bipartite Graphs Mivar Nets and Practical Realization of Automated Constructor of Algorithms Handling More than Three Million Production Rules

Oleg O. Varlamov, Moscow Automobile and Road State Technical University (MADI), Moscow Institute of Physics and Technologies (university) (MIPT), Russia.

Annotation. The theoretical transition from the graphs of production systems to the bipartite graphs of the MIVAR nets is shown. Examples of the implementation of the MIVAR nets in the formalisms of matrixes and graphs are given. The linear computational complexity of algorithms for automated building of objects and rules of the MIVAR nets is theoretically proved. On the basis of the MIVAR nets the UDAV software complex is developed, handling more than 1.17 million objects and more than 3.5 million rules on ordinary computers. The results of experiments that confirm a linear computational complexity of the MIVAR method of information processing are given.

Keywords: MIVAR, MIVAR net, logical inference, computational complexity, artificial intelligence, intelligent systems, expert systems, General Problem Solver.

Introduction

The problem of elaboration of intellectual systems is up-to-date and important. Elaboration of expert systems of new generation would allow automation of solving difficult problems. The MIVAR (Multidimensional Informational Variable Adaptive Reality) approach has provided an opportunity to offer new models and methods for data mining and management. The MIVAR technologies have been being elaborated in Russia for quite a long period of time. The first articles concerned some problems of graph theory and the elaboration of lineal matrix method of logic inference path finding on the adaptive net of rules [1-3]. Then, some work concerning the elaboration of MIVAR information space was done [4-5]. The most strictly formalized definition of the MIVARs can be found in papers [6-7]. Then the questions of the development [8-10] and the use of MIVARs for different simulators and instruction systems were discussed [11-22]. The fullest overview of theory and last achievements in MIVARs can be found in papers [4,6,10,15,18].

MIVAR nets allow the creation of new “General Problem Solver” the prototype of which is an UDAV (Universal Designer Algorithms Varlamov) programme complex. MIVAR nets remove restrictions existed before and, in fact, create expert systems of new generation which are capable to process millions of rules in acceptable time. MIVAR nets can be seen as a qualitative leap and transition to the new possibilities in information processing.

Let’s consider the systems of artificial intelligence as active self-learning logically thinking systems. In the last century, technologies of expert systems creating were elaborated for particular narrow subject domains. This was due to the difficulties in formalizing of required subjects domains as to the fact that systems of logic conclusion could not process more than 20 rules (because an exhaustive search is a Nondeterministically polynomical)