Nonlinear Pattern Matching in Rule-Based Modeling Languages

Rule-based modeling is an established paradigm for specifying simulation models of biochemical reaction networks. The expressiveness of rule-based modeling languages depends heavily on the expressiveness of the patterns on the left side of rules. Nonlinear patterns allow variables to occur multiple times. Combined with variables used in expressions, they provide great expressive power, in particular to express dynamics in discrete space. This has been exploited in some of the rule-based languages that were proposed in the last years. We focus on precisely defining the operational semantics of matching nonlinear patterns. We first adopt the usual approach to match nonlinear patterns by translating them to a linear pattern. We then introduce an alternative semantics that propagates values from one occurrence of a variable to other ones, and show that this novel approach permits a more efficient pattern matching algorithm. We confirm this theoretical result by benchmarking proof-of-concept implementations of both approaches.