The language of reaction rules (RR)

Syntax

A model is described in the RR language as:

• a series of variables declarations, gathered in sections
• a series of actions (constraints and rules)

A typical RR file will conform to the following structure:

# this is a comment that ends with the line
variables:
  # variables declarations
constraints:
  # actions declarations
rule:
  # actions declarations

Section variables: introduces some variables declarations. Section constraints: (resp. rules:) introduces constraints (resp. rules) declarations, if no constraints (resp. rules) are needed, the whole section including constraints: (resp. rules:) can be omitted. The text after every section has to be indented to mark the limits of the section. As in the example above, comments may be added either alone on a line, or at the end of a line with some other content.

Variables

The variables section is introduced with variables:, followed by a new line and an indented block with the variables declared in the section. Every variable has to be declared on a single line, conforming to one of the following patterns:

name+: textual description  # a variable that is initially on
name-: textual description  # a variable that is initially off
name*: textual description  # a variable for which we consider both initial states

Where name can be replaced with any variable name (starting with a letter and containing only letters, digits, or underscores _), and textual description is free text running until the end of the line (or until a comment) to describe the variable.

Declaring a variable name* causes the model to have two initial states: one where the variable is on and another where the variable is off. If another variable is declared this way, the model has four initial states, and so on with more variables declared this way.

Actions

Constraints and rules are declared exactly the same way, but in distinct sections. The pattern to declare an action is:

[tags] condition >> effect

where:

• tags is a comma-separated list of arbitrary strings that will be treated as action tags, these tags are like comments, but they are kept in the model and can be used during the analysis, the whole [tags] is optional
• condition is a comma-separated list of either var+ or var-, each putting a condition on one variable to be on or off
• assignment is a comma-separated list of either var+ or var-, each specifying the assignment of one variable to on or off

For instance, A+, B- >> C+ is an action that states that whenever A is on and B is off then C may be set to off.

Semantics

Starting from a set of initial states \(S_0\), the semantics defines how actions are fired to build the set of reachable states \(S\), or the state-space \((S,T)\) if we keep track of the fired actions. A state is defined as a vector of Boolean values, indexed by the variables of the model. At a state \(s\), an action \(a\) can be fired if:

• every condition of \(a\) is validated by \(s\)
• the state \(s'\), defined by applying onto \(s\) all the assignments in \(a\), is distinct from \(s\)

Firing \(a\) from \(s\) defines a transition \(s \xrightarrow{a} s'\). This allows to define inductively the state-space \((S,T)\) as the smallest pair of sets such that, \(S_0 \subseteq S\) and for all \(s \in S\):

• if there exists a constraint \(c\) such that \(s \xrightarrow{c} s'\) then \(s' \in S\) and \((s, c, s') \in T\)
• otherwise, if there exists a rule \(r\) such that \(s \xrightarrow{r} s'\) then \(s' \in S\) and \((s, r, s') \in T\)
• otherwise, \(s\) is called a deadlock

Note how this semantics defines the priority of constraints over rules: rules are allowed to fire only if none of the constraints can.

Ecosystemic hypergraph

The ecosystemic hypergraph of RR models can be made completely precise by choosing the arrow tips as follows:

condition	assignment	ecosystemic hypergraph
A+	no A
A+	A+
A+	A-
A-	no A
A-	A-
A-	A+
no A	A+
no A	A-

With this notation, it is easy to translate a model from the RR source to ecosystemic hypergraph, and vice-versa, which makes the ecosystemic hypergraph a notation semantically exact.

Petri nets semantics

The semantics defined above can be equivalently expressed by translating RR models to Petri nets. This opens the way to use unfolding based methods to analyze RR models as presented in Aguirre-Samboní et al, 2022. We give here an intuition about this translation and refer to Pommereau et al, 2022 for the full details.

To translate RR systems, we use a class of Petri nets with several extensions:

• transitions priorities: when a transition with a higher priority is enabled, transitions with a lower priority are inhibited
  • constraints are translated to transitions with higher priority
  • rules are translated to transitions with lower priority
• read arcs (sometimes called test arcs) can test the presence of a token in a place without consuming it; they are depicted as arcs without any tips
• inhibitor arcs test the absence of tokens in a place; they are depicted with a white dot instead of an arrowhead
• reset arcs empty a place may it contains tokens or no; they are depicted with a diamond instead of an arrowhead

With these extensions, every action is translated to a transition, every variable is translated to a place (whose marking is one token if the variable is initially on and no tokens otherwise), and the arcs are added depending on what is found in each side of every action:

condition	assignment	Petri net
A+	A+ or no A
A+	A-
A-	A- or no A
A-	A+
(no A)	A+
(no A)	A-

Note that this semantics does not allow for multiple initial states as Petri nets have no such feature. But we can equivalently consider that an RR model is translated to a family of Petri net that differ only by their initial markings.

It is show in Pommereau et al, 2022 that this translation preserves the semantics of the model: the state-space as defined above is exactly the same as the marking-graph of the Petri net (for one given initial state). Moreover, it is shown that the extended arcs used for the translation can be removed too by using a more complicated translation. Only priorities need to be kept if constraints are used.

Analysing RR models

Analyzing RR models will be better explained through example notebooks. Here, we present the main concepts and will refer to the appropriate notebooks for further details.

In general analysis techniques can be divided into two families:

• static analysis refer to techniques that involve the model as a description of a system whose dynamics is mostly ignored
• dynamic analysis refer to techniques that involve computing the reachable states of the model

In general, static analysis is less powerful than dynamic analysis as it does not exploit models’ dynamics, but it may yield interesting insights and may be applicable on models with so many reachable states that dynamic analysis becomes intractable.

Static analysis

The most basic analysis is to compute variables characterization, see Gaucherel et al, 2020. A variable is called fully characterized if it appears at least once as an action condition and at least once as an action assignment. In the ecosystemic graph, this means that this variable is both the source and the target of an edge, which means that is has influence on others and is itself influenced by others. Semi-characterized variables appear only on one side of an action:

• a variable that appear just as conditions but is never assigned is a constant, and can be considered as a parameter of the model
• a variable that appear just in assignments but is never used as a condition can be considered as an observable (it could be removed without changing the dynamics but may be useful to query during dynamic analysis)

ecco allows computing variables characterization and to display it as a bar chart showing how many times each variable is used as a condition or as an assignment.

See this notebook about static analysis

Drawing the ecosystemic graph and hypergraph can also be considered as static analysis as it allows to examine the model from specific perspectives, and ecco automates both. Other techniques as been developed, as searching patterns within models (eg, searching for a predator/prey pattern), see Di Giusto et al, 2019, but this is not integrated into ecco so far.

State-space analysis

Dynamic analysis in ecco is centered on component graphs: from a model we build a component graph and ecco provides methods to display it, explore its properties, and split/merge/drop its components to build new component graphs that can be explored in turn. This results in an interactive exploration method that allows to build incrementally a precise understanding of a model.

The main tool to explore a component graph is to split its components with respect to properties. ecco proposes several classes of properties:

• topological properties qualify the state-space as a graph to define subsets such as: the initial states, the deadlocks (states with no successors), the strongly connected components (SCC: maximal sets of states that are all reachable from one another), etc.
• temporal logic properties allow expressing properties about the dynamics. For instance ‘’all the states that have A+ and from which a state with B+ can be reached’’ is a property that can be expressed with temporal logic, it qualifies both a ‘’present’’ state (that has A+) and some states in its future (that can be reached from the present). ecco uses the Computation Tree Logic and some variants as its main temporal logic
• functional properties allows combining basic sets of states (as the initial states, SCCs, deadlocks, etc.) through the classical set operations as well as with various functions (as successor, predecessor, fixed points, etc.).

In every case, a property \(p\) is interpreted as a set of states \(S_p\). Moreover, a property is always evaluated with respect to the global states-space (unless it explicitly refers to sub-parts of it). So, every property \(p\) can be compared to each component \(C\), yielding one of the relations below:

ecco relation	Venn diagram	sets relation
HASNO		\(C \cap S_p = \emptyset\)
HAS		\(C \cap S_p \neq \emptyset\)
CONTAINS		\(C \supsetneq S_p\)
ISIN		\(C \subsetneq S_p\)
EQUALS		\(C = S_p\)

ecco allows to check a property \(p\) with respect to a component \(C\), which result in tagging \(C\) with the relation it has with \(S_p\). It is also possible to split \(C\) into \(C \cap S_p\) and \(C \setminus S_p\) (of course if either of this subset is empty, splitting is a no-op). Checks and splits of components, completed with merges and drops, are the basic operations to incrementally explore the behavior of a model.

See this notebook about incremental analysis