Formalization of basic pattern matching algorithms in production systems
DOI:
https://doi.org/10.15587/1729-4061.2015.46571Keywords:
pattern matching, formalization, Rete algorithm, Treat algorithm, production system, inferenceAbstract
Currently, there are several models of formalization of production systems. The formalization in terms of the first-order logic is the most universal. However, such formalization is not provided for all inference machinery in production systems. In particular, among the basic pattern matching algorithms, the generalized formal description was proposed only for the Rete algorithm. In the paper, the formalized description of the production system and basic matching algorithms (Rete, Treat) for further resource intensity assessment at the design stage was presented in a single format. A formal presentation of the compilation and implementation of the data flow network of the Treat algorithm was proposed. Based on the proposed formalization, the memory consumption calculation model for the Treat algorithm was extended due to taking into account memory consumption to preserve the conflict set and agree variables in the terminal vertices of the data flow network. In the future, the proposed single format of the presentation of the basic algorithms can be used for the resource intensity assessment of the Treat algorithm based on the mathematical models proposed for the Rete algorithm.
References
- Zhezhko, L., Jyejko, L., Karpik, A., Khoroshilov, V. (2005). Sistemy iskusstvennogo intellekta. Predstavleniye znaniy v informatsionnykh sistemakh. Novosibirsk: SGGA, 84.
- Kowalski, R., Sadri, F. (2010). Towards a Logic-based Production System Language. London. Available at: http://www.doc.ic.ac.uk/~fs/Papers/Reactive%20systems/LPS%20technical%20report.pdf
- Bulkin, V., Sharonova, N. (2006). Formal'noye predstavleniye znaniy v produktsionnykh sistemakh. Iskusstvennyy intellekt, 1, 147–157.
- Tao, Y., Zhijun, H., Ruizhao, Y. (1987). Artificial intelligence. Performance evaluation of the inference structure in expert system. San Francisco: Kaufmann Publishers Inc, 945–950.
- Shapovalova, S., Mazhara, O. (2014). Vybir optymalʹnoho alhorytmu spivstavlennya zi zrazkom pry proektuvanni produktsiynoyi systemy. Skhidno-Yevropeysʹkyy zhurnal peredovykh tekhnolohiy, 43–49. doi: 10.15587/1729-4061.2014.23338
- Dzharrantano, D., Rayli, G. (2007). Ekspertnyye sistemy: printsipy razrabotki i programirovaniye. Moskva: OOO «I.D. Vil'yams», 1152.
- Forgy, C. (1979). On the Efficient Implementation of Production System : PhD thesis. Pittsburg: Carnegie Mellon University Computer Science, 356.
- Miranker, D. P. (1990). TREAT: A New and Efficient Match Algorithm for AI Production Systems. London: Pitman, 144.
- Liu, D., Gu, T., Xue, J.-P. (2010). Rule Engine based on improvement Rete algorithm. The 2010 International Conference on Apperceiving Computing and Intelligence Analysis Proceeding, 346–349. doi: 10.1109/icacia.2010.5709916
- Berstel, B. (2002). Extending the RETE algorithm for event management. Proceedings Ninth International Symposium on Temporal Representation and Reasoning. doi: 10.1109/time.2002.1027472
- Kang, J. A., Mo, A., Cheng, K. (2004). Shortening Matching Time in OPS5 Production Systems. IEEE Transactions on Software Engineering, 30 (7), 448–457. doi: 10.1109/tse.2004.32
- Albert, L., Fages, F. (1988). Average case complicity analyzes of the Rete multi-pattern match algorithm. Automata, Languages and Programming 5th International Colloquium Tampere. Finland, 18–37. doi: 10.1007/3-540-19488-6_104
- Cirstea, H., Kirchner, C., Moossen, M., Moreau, P. E. (2004). Production Systems and Rete Algorithm Formalisation. Available at: https://hal.inria.fr/file/index/docid/280938/filename/rete.formalisation.pdf
- Wright, I. (2003). The execution kernel of rc++: Rete*, a faster rete with treat as special case. International Journal of Intelligent Games and Simulation, 36–48.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Світлана Ігорівна Шаповалова, Ольга Олександрівна Мажара
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
