Formalization of Basic Pattern Matching Algorithms in Production Systems

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