S.D. Makhortov - Dr. Sc. (Phys.-Math.), Associate Professor, Head of Department of Applied and System Software, Voronezh State University. E-mail: sd@expert.vrn.ru

Algebraic structures provide effective tools for formalization and research of informational systems that related to various para-digms, including a separate class of intelligent systems. These tools can be applied particularly to such part of these systems as presenting knowledge and theories. One of the most advanced ways of logic systems formalization and researching is based on the "algebraization of logic" ? a special algebraic way of describing a model of knowledge and the rules of inference. It allows solving important problems such as verification and optimization of the knowledge bases using abstract mathematical methods. One of the classical examples is the Lindenbaum-Tarski theory, which considers the logic of statements as a universal algebra, operations of which correspond to logical relations of the propositional language. At the same time, due to it-s versatility alge-braic logic does not solve many important problems related to the commonly used production systems. For the research of such systems, author proposes algebraic structures that allow formalizing the production logical inference using the theory of lattices and binary relations. The idea is based on defining two relations on a common set. The first relation is constant in the current mode and it determines the lattice by setting the partial order on it. The second relation is generated by a particular subject area and can be modified in order to optimize it. These relationships can be characterized as transitive and monotony that are the properties of a standard production logical inference; therefore these relationships are called logical relationships. A lattice with a defined logical relation is called an LP-structure (Lattice Production Structure). During the research of such structures author obtained results which allow to substantiate and automate such production logical system tasks as the equivalent transformation, optimization, verification, efficient backward inference. Further research showed the opportunity to apply this approach to a number of different tasks in computer science because many models in fact have productional nature and structures that represent information are hierarchical in the same way as lattices. The purpose of this article is to introduce the LP-structure theory and present a brief overview of its application and development prospects. It introduces the basic concepts related to the binary relations, lattices and production systems. It also describes a number of problems in various areas of computer science, which can be presented as production systems simulated by LP-structures and then researched using the same structures or their modifications.

 

1. CHechkin A.V. Matematicheskaja informatika. M.: Fizmatlit. 1991. 416 s.
2. Beniaminov E.M. Algebraicheskie metody v teorii baz dannykh i predstavlenii znanijj. M.: Nauchnyjj mir. 2003. 184 s.
3. Raseva E., Sikorskijj R. Matematika metamatematiki: Per. s angl. M.: Nauka. 1972. 591 s.
4. Davis R., King J. An overview of production systems // Machine Intelligence. 1977. V. 8, Ellis Horwood Limited, Chichester. P. 300-332.
5. MakhortovS.D.Logicheskieotnoshenijanareshetkakh// VestnikVGU. Ser. Fizika, matematika. Voronezh. 2003. №2. S. 203-209.
6. Aho A.V., Garey M.R., Ulman J.D. The transitive reduction of a directed graph // SIAM J. Computing. 1972. V. 1. № 2. P. 131-137.
7. Doorenbos R.B.Production Matching for Large Learning Systems. Doctoral Thesis. UMI Order Number: UMI Order No. GAX95-22942. CarnegieMellonUniversity. 1995.
8. Sojjer B., Foster D.L. Programmirovanie ehkspertnykh sistem na Paskale: Per. s angl. M.: Finansy i statistika. 1990. 191 s.
9. Makhortov S.D. Logicheskie uravnenija na reshetkakh // Vestnik VGU. Ser. Fizika, matematika. Voronezh. 2004. № 2. S. 170-178.
10. Bolotova S.JU., Makhortov S.D. Algoritmy relevantnogo obratnogo vyvoda, osnovannye na reshenii produkcionno-logicheskikh uravnenijj // Iskusstvennyjj intellekt i prinjatie reshenijj. 2011. № 2. S. 40-50.
11. Bolotova S.JU., Makhortov S.D. Parallelnye algoritmy relevantnogo LP-vyvoda // Programmnaja inzhenerija. 2014. № 7. S. 17-24.
12. Makhortov S.D. Ob algebraicheskojj interpretacii produkcionnojj logiki nulevogo porjadka // Vestnik VGU. Serija sistemnyjj analiz i informacionnye tekhnologii. Voronezh. 2007. № 1. S. 56-63.
13. Ivanov I.JU. O priblizhennom reshenii produkcionno-logicheskogo uravnenija na bulevojj reshetke // Nejjrokompjutery. Razrabotka, primenenie. 2014. № 10. S. 53-63.
14. Makhortov S.D.Produkcionnaja logika pervogo porjadka i ee algebraicheskaja interpretacija // Sistemy upravlenija i informacionnye tekhnologii. 2007. № 3(29). S. 21-26.
15. Nemeti I. Algebraization of Quantifier Logics; an Overview // Studia Logica L. 1991. Nos3/4. S. 485-569.
16. Tejjz A., Gribomon P. i dr. Logicheskijj podkhod k iskusstvennomu intellektu: ot klassicheskojj logiki k logicheskomu programmirovaniju: Per. s franc. M.: Mir. 1990. 432 s.
17. Sowa J.F. Conceptual Structures: Information Processing in Mind and Machine. Reading, MA: Addison-Wesley. 1984.
18. Fauler M., Skott K.UML. Osnovy: Per. s angl. SPb: Simvol-Pljus. 2002. 192 s.
19. Makhortov S.D.LP-struktury na reshetkakh tipov i nekotorye zadachi refaktoringa // Programmirovanie. 2009. № 4. S. 5-14.
20. Makhortov S.D. LP-struktury dlja obosnovanija i avtomatizacii refaktoringa v obektno-orientirovannom programmirovanii // Programmnaja inzhenerija. 2010. № 2. S. 15-21.
21. Makhortov S.D., Shurlin M.D. LP-structures analysis: Substantiation of refactoring in object-oriented programming // Automation and Remote Control. 2013. V. 74. № 7. P. 1211-1217.
22. Schmitt P.H., A Survey of Rewrite Systems. In Proceedings of the 1st Workshop on Computer Science Logic (October 12 - 16, 1987). Börger E., Büning H. K., Richter M. M., Eds. Lecture Notes In Computer Science, V. 329. Springer-Verlag, London. R. 235-262.
23. Dershowitz N., Okada M.,Sivakumar G. Canonical Conditional Rewrite Systems. In Proceedings of the 9th international Conference on Automated Deduction (May 23-26, 1988).E. L. Lusk and R. A. Overbeek (Eds). Lecture Notes In Computer Science. V. 310. Springer-Verlag. London. 1988. R. 538-549.
24. Makhortov S.D. Osnovannyjj na reshetkakh podkhod k issledovaniju i optimizacii mnozhestva pravil uslovnojj sistemy perepisyvanija termov // Intellektualnye sistemy. 2009. T. 13. Vyp. 1-4. S. 51-68.
25. Baranov D.V. Logicheskie uravnenija v ehkvacionalnykh LP-strukturakh // Informacionnye tekhnologii. 2012. № 8. C. 35-42.
26. CHechkin A.V. Nejjrokompjuternaja paradigma informatiki // Nejjrokompjutery: razrabotka, primenenie. 2011. № 7. S. 3-9.
27. Makhortov S.D., SHmarin A.N. Nechetkijj LP-vyvod i ego programmnaja realizacija // Programmnaja inzhenerija. 2013. № 12. S. 34-38.