Cause-Effect Structures Behaving like Reaction
Systems
Ludwik Czaja1,2
1
    Vistula University, Warsaw, Poland
2
    Institute of Informatics, The University of Warsaw, Poland


                                         Abstract
                                         Cause-effect (c-e) structures, a net-like algebraic formalism for describing and analysing systems, pri-
                                         marily parallel, may be adapted to work as Reaction Systems. This is acquired by a simple modification
                                         of the c-e structures’ semantics

                                         Keywords
                                         cause-effect structure, reaction system, quasi semiring



           1. Summary of elementary cause-effect structures

   Cause-effect structures (c-e) are objects of an algebraic calculus called a quasi-semiring1 , for
describing and analysing systems built up as nets. Among a number of similarities to Petri nets,
the noticeable is graphic presentation of systems’ dynamics. The complete presentation of c-e
structures is in [Cza 2019].

           Definition 1.1 (set F [X], quasi-semiring of formal polynomials)

   Let X be a non-empty enumerable set. Its elements, called nodes, are counterparts of places in
Petri nets. 𝜃 ∈
              / X is a symbol called neutral. It plays role of neutral element for operations on
terms, called formal polynomials over X. The names of nodes, symbol 𝜃, operators +, ∙, called
addition and multiplication, and parentheses are symbols out of which formal polynomials
are formed. A node’s name and 𝜃 is a formal polynomial; if 𝐾 and 𝐿 are formal polynomials,
then (𝐾 + 𝐿) and (𝐾 ∙ 𝐿) are too. Their set is denoted by F [X]. Assume stronger binding of ∙
than +, which allows for dropping some parentheses. Addition and multiplication of formal
polynomials is defined as follows: 𝐾 ⊕ 𝐿 = (𝐾 + 𝐿), 𝐾 ⊙ 𝐿 = (𝐾 ∙ 𝐿). To simplify notation,
let us use + and ∙ instead of ⊕ and ⊙. It is required that the system ⟨F [X], +, ∙, 𝜃⟩ obeys the
following equality axioms for all 𝐾, 𝐿, 𝑀 ∈ F [X], 𝑥 ∈ X:
(+)     𝜃+𝐾 =𝐾 +𝜃 =𝐾                         (∙)    𝜃∙𝐾 =𝐾 ∙𝜃 =𝐾

29th International Workshop on Concurrency, Specification and Programming (CS&P’21)
" lczaja@mimuw.edu.pl (L. Czaja)
 0000-0003-4675-816X (L. Czaja)
                                       © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR

           CEUR Workshop Proceedings (CEUR-WS.org)
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073




                  1
      This calculus differs from the standard semiring by restricted distributivity law: 𝑎 · (𝑏 + 𝑐) = 𝑎 · 𝑏 + 𝑎 · 𝑐
satisfied provided that 𝑏 ̸= 𝜃 if and only if 𝑐 ̸= 𝜃 where 𝜃 is a neutral element for both operations (simultaneity
and nondeterministic choice). Hence the preposition "quasi". Note that due to the conditional distributivity, the
calculus neither reduces to the single element 𝜃, nor makes both operations coincide.
(++) 𝐾 + 𝐾 = 𝐾                           (∙∙) 𝑥 ∙ 𝑥 = 𝑥
(+++) 𝐾 + 𝐿 = 𝐿 + 𝐾                     (∙ ∙ ∙) 𝐾 ∙ 𝐿 = 𝐿 ∙ 𝐾
(++++) 𝐾 + (𝐿 + 𝑀 ) = (𝐾 + 𝐿) + 𝑀 (∙ ∙ ∙∙) 𝐾 ∙ (𝐿 ∙ 𝑀 ) = (𝐾 ∙ 𝐿) ∙ 𝑀
(+∙)    If 𝐿 ̸= 𝜃 ⇔ 𝑀 ̸= 𝜃 then 𝐾 ∙ (𝐿 + 𝑀 ) = 𝐾 ∙ 𝐿 + 𝐾 ∙ 𝑀
  Algebraic system which obeys these axioms will be referred to as a quasi-semiring of formal
polynomials.                                                                               □

  Definition 1.2 (cause-effect structure, carrier, set CE[X])

A cause-effect structure (c-e structure) over X is a pair 𝑈 = ⟨𝐶, 𝐸⟩ of total functions:

𝐶: X → F [X]           (cause function; nodes occuring in 𝐶(𝑥) are causes of 𝑥)
𝐸: X → F [X]           (effect function; nodes occuring in 𝐸(𝑥) are effects of 𝑥)

such that 𝑥 occurs in the formal polynomial 𝐶(𝑦) iff 𝑦 occurs in 𝐸(𝑥). Carrier of 𝑈 is the
set 𝑐𝑎𝑟(𝑈 ) = {𝑥 ∈ X : 𝐶(𝑥) ̸= 𝜃 ∨ 𝐸(𝑥) ̸= 𝜃}. 𝑈 is of finite carrier iff |𝑐𝑎𝑟(𝑈 )| < ∞ (|...|
denotes cardinality). The set of all c-e structures over X is denoted by CE[X]. Since X is fixed,
we write just CE.                                                                              □

𝐶 and 𝐸 are total, thus each c-e structure comprises all nodes from X, also the isolated ones
- those from outside of its carrier. In presenting c-e structures graphically, only their carriers
are drawn. A representation of a c-e structure 𝑈 = ⟨𝐶, 𝐸⟩ as a set of annotated nodes is
    𝐶(𝑥)
{𝑥𝐸(𝑥) : 𝑥 ∈ 𝑐𝑎𝑟(𝑈 )}. 𝑈 is also presented as a directed graph with 𝑐𝑎𝑟(𝑈 ) as set of vertices
                                          𝐶(𝑥)
labelled with objects of the form 𝑥𝐸(𝑥) (𝑥 ∈ 𝑐𝑎𝑟(𝑈 )); there is an edge from 𝑥 to 𝑦 iff 𝑦 occurs
in the polynomial 𝐸(𝑥). Fig. 1 (a) and (b) depict two graphical presentations of the same c-e
structure with carrier {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ}; in (a) the encircled nodes comprise groups making
products in formal polynomials in (b), where the sums of the products create families of the
groups. This c-e structure is the set {𝑎𝜃𝑒 , 𝑏𝜃𝑒 , 𝑐𝜃𝑒 , 𝑑𝜃𝑒 , 𝑒𝑎+𝑏·𝑐+𝑐·𝑑
                                                                𝑓 ·𝑔+ℎ    , 𝑓𝜃𝑒 , 𝑔𝜃𝑒 , ℎ𝑒𝜃 }. Sometimes the empty
subscript/superscript 𝜃 by node names is omitted.




Figure 1: (a) Predecessors and successors of the node 𝑒, grouped into families:
{{𝑎}, {𝑏, 𝑐}, {𝑐, 𝑑}} and {{𝑓, 𝑔}, {ℎ}}. (b) Notation by means of polynomials; the arrows are redun-
dant: used only for graphic presentation of c-e structures.
   Definition 1.3 (addition and multiplication, monomial c-e structure)

For c-e structures 𝑈 = ⟨𝐶𝑈 , 𝐸𝑈 ⟩, 𝑉 = ⟨𝐶𝑉 , 𝐸𝑉 ⟩                    define:
𝑈 + 𝑉 = ⟨𝐶𝑈 +𝑉 , 𝐸𝑈 +𝑉 ⟩ = ⟨𝐶𝑈 + 𝐶𝑉 , 𝐸𝑈 + 𝐸𝑉 ⟩                        where
(𝐶𝑈 + 𝐶𝑉 )(𝑥) = 𝐶𝑈 (𝑥) + 𝐶𝑉 (𝑥) and similarly for 𝐸
𝑈 ∙ 𝑉 = (𝐶𝑈 ∙𝑉 , 𝐸𝑈 ∙𝑉 ) = (𝐶𝑈 ∙ 𝐶𝑉 , 𝐸𝑈 ∙ 𝐸𝑉 )                       where
(𝐶𝑈 ∙ 𝐶𝑉 )(𝑥) = 𝐶𝑈 (𝑥) ∙ 𝐶𝑉 (𝑥) and similarly for 𝐸

(The same symbols "+" and "∙" are used for operations on c-e structures and formal polynomials).
𝑈 is a monomial c-e structure iff each polynomial 𝐶𝑈 (𝑥) and 𝐸𝑈 (𝑥) is a monomial, i.e. does
not comprise non-reducible (relative to equations in Definition 1.1) operation “+“.          □

  Apart from the representation of c-e structures as a set
  𝐶(𝑥)
{𝑥𝐸(𝑥) : 𝑥 ∈ 𝑐𝑎𝑟(𝑈 )}, their linear notation is used as the so-called "arrow-expressions":
{𝑥𝜃𝑦 , 𝑦𝜃𝑥 } is an arrow, denoted as 𝑥 → 𝑦 and, consequently, {𝑥𝜃𝑦 , 𝑦𝜃𝑥 } ∙ {𝑦𝑧𝜃 , 𝑧𝜃𝑦 }∙{𝑧𝑢𝜃 , 𝑢𝑧𝜃 }..... =
{𝑥𝜃𝑦 , 𝑦𝑧𝑥 , 𝑧𝑢𝑦 , 𝑢𝑧.... .....} is a chain, denoted as 𝑥 → 𝑦 → 𝑧 → 𝑢.... . Bidirectional arrow 𝑥 ↔ 𝑦
denotes 𝑥 → 𝑦 → 𝑥 (equivalent to 𝑦 → 𝑥 → 𝑦), that is, the close cycle {𝑥𝑦𝑦 , 𝑦𝑥𝑥 }. Chains
and arrows in particular, may be combined into “arrow expressions” representing some c-e
structures. For instance c-e structure {𝑎𝜃𝑥+𝑦 , 𝑏𝜃𝑥∙𝑦 , 𝑥𝑎∙𝑏  𝜃 , 𝑦𝜃 } may be written as
                                                                   𝑎∙𝑏

(𝑎 → 𝑥 + 𝑎 → 𝑦) ∙ (𝑏 → 𝑥) ∙ (𝑏 → 𝑦).

   The set CE with addition, multiplication and a distinguished element denoted also by 𝜃 and
understood as the empty c-e structure (𝜃, 𝜃), where 𝜃 is a constant function 𝜃(𝑥) = 𝜃 for all
𝑥 ∈ X, makes an algebraic system similar to that in Definition 1.1, the quasi-semiring of c-e
structures. Therefore the Proposition 1.1:

Proposition 1.1 The system ⟨CE[X], +, ∙, 𝜃⟩ obeys the following equations for all 𝑈, 𝑉, 𝑊 ∈
CE[X], 𝑥, 𝑦 ∈ X:

(+)    𝜃+𝑈 =𝑈 +𝜃 =𝑈                     (∙)      𝜃∙𝑈 =𝑈 ∙𝜃 =𝑈
(++)   𝑈 +𝑈 =𝑈                           (∙∙)      (𝑥 → 𝑦) ∙ (𝑥 → 𝑦) = 𝑥 → 𝑦
(+++) 𝑈 + 𝑉 = 𝑈 + 𝑉                     (∙ ∙ ∙) 𝑈 ∙ 𝑉 = 𝑉 ∙ 𝑈
(++++) 𝑈 + (𝑉 + 𝑊 ) = (𝑈 + 𝑉 ) + 𝑊        (∙ ∙ ∙∙) 𝑈 ∙ (𝑉 ∙ 𝑊 ) = (𝑈 ∙ 𝑉 ) ∙ 𝑊
(+∙)   If 𝐶𝑉 (𝑥) ̸= 𝜃 ⇔ 𝐶𝑊 (𝑥) ̸= 𝜃 and 𝐸𝑉 (𝑥) ̸= 𝜃 ⇔ 𝐸𝑊 (𝑥) ̸= 𝜃 then
       𝑈 ∙ (𝑉 + 𝑊 ) = 𝑈 ∙ 𝑉 + 𝑈 ∙ 𝑊                                                                       □

  Definition 1.4 (partial order ≤; substructure, set SUB[𝑉 ], firing component, set FC, pre-set
and post-set)

For 𝑈, 𝑉 ∈ CE let 𝑈 ≤ 𝑉 ⇔ 𝑉 = 𝑈 + 𝑉 ; ≤ is a partial order in CE. If 𝑈 ≤ 𝑉 then 𝑈 is a
substructure of 𝑉 ; SUB[𝑉 ]= {𝑈 : 𝑈 ≤ 𝑉 } is the set of all substructures of 𝑉 . For 𝐴 ⊆CE:
𝑉 ∈ 𝐴 is minimal (wrt ≤) in 𝐴 iff ∀𝑊 ∈ 𝐴: (𝑊 ≤ 𝑉 ⇒ 𝑊 = 𝑉 ).
A minimal in CE∖{𝜃} c-e structure 𝑄 = ⟨𝐶𝑄 , 𝐸𝑄 ⟩ is a firing component iff 𝑄 is a monomial c-e
structure and 𝐶𝑄 (𝑥) = 𝜃 ⇔ 𝐸𝑄 (𝑥) ̸= 𝜃 for any 𝑥 ∈ 𝑐𝑎𝑟(𝑄). The set of all firing components
is denoted by FC, thus the set of all firing components of 𝑈 ∈CE is FC[𝑈 ] = SUB[𝑈 ] ∩ FC.
Let for 𝑄 ∈ FC and 𝐺 ⊆ FC:
∙ 𝑄 = {𝑥 ∈ 𝑐𝑎𝑟(𝑄) : 𝐶
                    𝑄 (𝑥) = 𝜃}                (pre-set or causes of 𝑄)
𝑄∙ = {𝑥 ∈ 𝑐𝑎𝑟(𝑄) : 𝐸𝑄 (𝑥) = 𝜃}                (post-set or effects of 𝑄)
∙ 𝑄∙ = ∙ 𝑄 ∪ 𝑄∙
∙𝐺 =                                           (pre-set or causes of 𝐺)
       ⋃︀ ∙
            𝑄
      𝑄∈𝐺
𝐺∙ =      𝑄∙                                  (post-set or effects of 𝐺)
       ⋃︀
      𝑄∈𝐺
∙ 𝐺∙ = ∙ 𝐺 ∪ 𝐺∙                                                                                   □

Thus, the firing component is a connected graph, due to the required minimality. Elements of
the pre-set are its causes and elements of the post-set are its effects.

  Definition 1.5 (salvo - pairwise detached firing components; family FCS)

Firing components 𝑄 and 𝑃 are detached if and only if ∙ 𝑄∙ ∩ ∙ 𝑃 ∙ = ∅. Any set 𝐺 ⊆FC of
pairwise detached firing components is called their salvo. The family of salvos is denoted by
FCS. So, if 𝐺 ⊆FC[𝑈 ] then FCS[𝑈 ] ⊆ 2FC[𝑈 ] for a c-e structure 𝑈 , denotes a collection of
salvos in 𝑈 . The intention is that firing components in a salvo are capable of acting ("firing")
simultaneously. This notion will be used in definition of parallel semantics of c-e structures.□

  Definition 1.6 (state of elementary c-e structures)

  A state is a subset of the set of nodes: 𝑠 ⊆ X. The set of all states: S = 2X . A node 𝑥 is
active in the state 𝑠 iff 𝑥 ∈ 𝑠 and passive otherwise. As in case of Petri nets, we say ”𝑥 holds a
token” when 𝑥 is active. Obviously, the state might be defined equivalently as a two-valued
function 𝑠: X →{0, 1}.                                                                          □

  Definition 1.7 (sequential and parallel semantics of elementary c-e structures)

Sequential. For 𝑄 ∈FC[𝑈 ] , 𝑠 ∈ S, let [[𝑄]] ⊆ S × S be a binary relation defined as:
(𝑠, 𝑡) ∈ [[𝑄]] iff ∙ 𝑄 ⊆ 𝑠 ∧ 𝑄∙ ∩ 𝑠 = ∅ ∧ 𝑡⋃︀= (𝑠∖∙ 𝑄) ∪ 𝑄∙ (𝑄 transforms state 𝑠 into 𝑡).
Semantics [[𝑈 ]] of 𝑈 ∈CE is: [[𝑈 ]] =          [[𝑄]]. [[𝑈 ]]* is its reflexive and transitive
                                            𝑄∈FC [𝑈 ]
closure, that is (𝑠, 𝑡) ∈ [[𝑈 ]]* if and only if 𝑠 = 𝑡 or there exists a sequence of states
𝑠0 , 𝑠1 , ..., 𝑠𝑛 with 𝑠 = 𝑠0 , 𝑡 = 𝑠𝑛 and (𝑠𝑗 , 𝑠𝑗+1 ) ∈ [[𝑈 ]] for 𝑗 = 0, 1, ..., 𝑛 − 1. State 𝑡 is
reachable from 𝑠 in semantics [[ ]] and the sequence 𝑠0 , 𝑠1 , ..., 𝑠𝑛 is a computation performed
by 𝑈 .
Parallel. For a salvo 𝐺 ∈FCS[𝑈 ], 𝐺 ̸= ∅, relations [[𝐺]] and [[𝑈 ]]𝑝𝑎𝑟 are defined in the
same way as [[𝑄]] and [[𝑈 ]] in the sequential case but with 𝑄 replaced with 𝐺 and FC[𝑈 ]
replaced with FCS[𝑈 ]. Closure [[𝑈 ]]*𝑝𝑎𝑟 , reachability and computation are defined as in the
sequential case.                                                                                   □

Note that [[𝑈 ]] = ∅ iff FC[𝑈 ] = ∅. Behaviour of elementary c-e structures may be thought
of as a token game: if each node in a firing component’s pre-set holds a token and none in
its post-set does, then remove tokens from the pre-set and put them in the post-set. This is
illustrated in Fig. 2. Properties inferred from above definitions are proved in [Cza 2019].




Figure 2: Example of activity (successive transformations) of elementary c-e structure. Its linear nota-
tion as an "arrow expression" is the following:
(𝑎 → 𝑏) + (𝑏 → 𝑐) ∙ (𝑏 → 𝑑) + (𝑏 → 𝑒) + (𝑐 → 𝑒) + (𝑐 → 𝑑) + (𝑒 → 𝑑) + (𝑒 → 𝑎).




  2. Summary of extended cause-effect structures

   The structure of extended c-e structures, their firing component in particular, is the same
as in Definitions 1.1 - 1.4. The extensions consist in redefining the state, treating the pre and
post sets of firing components as multisets, and redefining semantics. It is assumed that with a
given c-e structure 𝑈 ∈CE[X] (i.e. already constructed by operations introduced in Definition
1.3) and the set of its firing components FC[𝑈 ] = SUB[𝑈 ]∩FC, some additional information is
associated. The following extensions of elementary c-e structures with this information will be
obtained: multi-valued nodes, capacity of nodes and coefficients of monomials in polynomials
annotating nodes (counterparts of weight of arrows in Petri nets), in particular a coefficient 𝜔
which represents inhibiting. To this end, a notation for multisets is convenient: let N be the set
of natural numbers including 0 and N𝜔 = N ∪ {𝜔}, where the value 𝜔 means infinity, that
is 𝜔 > 𝑛 for each 𝑛 ∈ N. A multiset over a base set 𝑋 is a (total) function 𝑓 : 𝑋 → N𝜔 . If
the set {𝑥: 𝑓 (𝑥) ̸= 0} is finite then the linear-form notation is adopted for multisets , e.g.
  𝑋        𝑎 𝑏 𝑐 𝑑 𝑒
                                  is denoted by 2 ⊗ 𝑎 + 3 ⊗ 𝑐 + 𝑑 + 𝜔 ⊗ 𝑒. A multiset is zero
  𝑓 (𝑋) 2 0 3 1 𝜔
O, when O(𝑥) = 0 for all 𝑥. Addition, subtraction and multiplication on multisets is defined:
(𝑓 +𝑔)(𝑥) = 𝑓 (𝑥)+𝑔(𝑥), (𝑓 −𝑔)(𝑥) = 𝑓 (𝑥)−𝑔(𝑥) for 𝑓 (𝑥) ≥ 𝑔(𝑥), (𝑓 ·𝑔)(𝑥) = 𝑓 (𝑥)·𝑔(𝑥),
comparison of multisets: 𝑓 ≤ 𝑔 iff 𝑓 (𝑥) ≤ 𝑔(𝑥) for all 𝑥. Assume the customary arithmetic
of 𝜔: 𝜔 + 𝑛 = 𝜔, 𝜔 − 𝑛 = 𝜔, 𝜔 + 𝜔 = 𝜔 and additionally 0 − 𝜔 = 0.

Definition 2.1 (state of extended c-e structures)

A state of extended c-e structure 𝑈 is a total function 𝑠 : 𝑐𝑎𝑟(𝑈 ) → N, thus a multiset over
𝑐𝑎𝑟(𝑈 ). The set of all states of 𝑈 is denoted by S.                                       □

Definition 2.2. (weights of monomials and capacity of nodes)

For a c-e structure 𝑈 = ⟨𝐶, 𝐸⟩ and its firing component 𝑄 ∈FC[𝑈 ], let with the pre-set ∙ 𝑄
and post-set 𝑄∙ of 𝑄, some multisets ∙ 𝑄: ∙ 𝑄 → N𝜔 and 𝑄∙ : 𝑄∙ → N𝜔 be given as additional
information. The value ∙ 𝑄(𝑥) is a weight (or multiplicity) of monomial 𝐸𝑄 (𝑥) and the value
𝑄∙ (𝑥) - a weight (or multiplicity) of monomial 𝐶𝑄 (𝑥). For 𝐸𝑄 (𝑥) = 𝜃 or 𝐶𝑄 (𝑥) = 𝜃
assume respectively ∙ 𝑄(𝑥) = 0 or 𝑄∙ (𝑥) = 0 and additionally let ∙ 𝑄(𝑥) = 0 for 𝑥 ∈      / ∙𝑄
and 𝑄 (𝑥) = 0 for 𝑥 ∈
        ∙                / 𝑄 . Let 𝑐𝑎𝑝(𝑈 ) be a total function 𝑐𝑎𝑝(𝑈 ) : 𝑐𝑎𝑟(𝑈 ) → N𝜔 ∖{0},
                              ∙

assigning a capacity to nodes in the set 𝑐𝑎𝑟(𝑈 ). A c-e structure endowed with such information
is a c-e structure-with-weighted monomials and capacity of nodes. Note that this definition
extends directly from the firing components onto their salvos. Indeed, For any non-empty salvo
𝐺 ∈FCS[𝑈 ] and any 𝑥 ∈ ∙ 𝐺∙ there exists exactly one firing component 𝑄 ∈ 𝐺, with 𝑥 ∈
∙ 𝑄∙ (because firing components in 𝐺 are pairwise detached). Thus one may define ∙ 𝐺 = ∙ 𝑄

and 𝐺∙ = 𝑄∙ . It should also be noticed that weights of cause or effect monomials in identical
firing components appearing in different c-e structures, may be different.                    □

An effect monomial 𝐸𝑄 (𝑎) of a node 𝑎 ∈ ∙ 𝑄, with weight ∙ 𝑄(𝑎), is denoted by ∙ 𝑄(𝑎)⊗𝐸𝑄 (𝑎).
Similarly for a cause monomial 𝐶𝑄 (𝑥) of a node 𝑥 ∈ 𝑄∙ with weight 𝑄∙ (𝑥): 𝑄∙ (𝑥) ⊗ 𝐶𝑄 (𝑥).
The coefficient representing weights will be abandoned if they are 1.

Definition 2.3 (inhibitors)

For a firing component 𝑄 ∈FC[𝑈 ], let 𝑖𝑛ℎ[𝑄] = {𝑥 ∈ ∙ 𝑄 : ∙ 𝑄(𝑥) = 𝜔}, thus a set of nodes
in the pre-set of 𝑄, whose effect monomials 𝐸𝑄 (𝑥) are of weight 𝜔. The nodes in 𝑖𝑛ℎ[𝑄] will
play role of inhibiting nodes of firing component 𝑄. In accordance with the note in Definition
1.5 (pairwise detached firing components in salvos), the concept of inhibiting nodes extends
directly onto the salvos: 𝑖𝑛ℎ[𝐺] = {𝑥 ∈ ∙ 𝐺 : ∙ 𝐺(𝑥) = 𝜔} where 𝐺 ∈FCS[𝑈 ]. The inhibiting
nodes will be called inhibitors.                                                             □

Definition 2.4. (enabled firing components and enabled salvos)

For a firing component 𝑄 ∈FC[𝑈 ] and state 𝑠 let us define the formula: 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝑄](𝑠) if and
only if:

  ∀𝑥 ∈ 𝑖𝑛ℎ[𝑄] : 𝑠(𝑥) = 0∧
  ∀𝑥 ∈ ∙ 𝑄∖𝑖𝑛ℎ[𝑄] : 𝑠(𝑥) > 0 ∧ ∙ 𝑄(𝑥) ≤ 𝑠(𝑥) ≤ 𝑐𝑎𝑝(𝑈 )(𝑥)∧
  ∀𝑥 ∈ 𝑄∙ : 𝑄∙ (𝑥) + 𝑠(𝑥) ≤ 𝑐𝑎𝑝(𝑈 )(𝑥)

So, 𝑄 is enabled in the state 𝑠 iff none of inhibiting nodes 𝑥 ∈ ∙ 𝑄 contains a token and each
remaining node in ∙ 𝑄 contains, with no fewer tokens than is the weight of its effect monomial
𝐸𝑄 (𝑥) and no more than capacity of each 𝑥 ∈ ∙ 𝑄. Moreover, none of 𝑥 ∈ 𝑄∙ holds more
tokens than their number when increased by the weight of the cause monomial 𝐶𝑄 (𝑥), exceeds
capacity of 𝑥. Evidently, for a salvo 𝐺 ∈FCS[𝑈 ], the formula 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝐺](𝑠) is defined as
above by replacing 𝑄 with 𝐺 and FC[𝑈 ] with FCS[𝑈 ].                                        □

Definition 2.5. (Sequential and parallel semantics of extended c-e structures)

Sequential. For 𝑄 ∈FC[𝑈 ] , let [[𝑄]] ⊆ S × S be a binary relation defined as:
(𝑠, 𝑡) ∈ [[𝑄]] iff 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝑄](𝑠) ∧ 𝑡 = (𝑠 − ∙ 𝑄)
                                              ⋃︀ + 𝑄 ≤ 𝑐𝑎𝑝(𝑈 ) (𝑄 transforms
                                                     ∙                          state 𝑠 into
𝑡). Semantics [[𝑈 ]] of 𝑈 ∈CE is [[𝑈 ]] =         [[𝑄]]. Closure [[𝑈 ]] and reachability and
                                                                       *
                                                𝑄∈FC[𝑈 ]
computation are defined as in Definition 1.7.
Parallel. For a salvo 𝐺 ∈FCS[𝑈 ], 𝐺 ̸= ∅, the relations [[𝐺]] and [[𝑈 ]]𝑝𝑎𝑟 are defined in
the same way as [[𝑄]] and [[𝑈 ]] in the sequential case, but with 𝑄 replaced with 𝐺 and FC[𝑈 ]
replaced with FCS[𝑈 ]. Closure [[𝑈 ]]*𝑝𝑎𝑟 , reachability and computation are defined as in the
sequential case.                                                                            □

   An example of using inhibitor is in Fig. 3. The weight of one effect (i.e. subscript) monomial
𝜔 ⊗ 𝑧 of the node 𝑇 is 𝜔, thus traversing arrow from 𝑇 to 𝑧 would require infinite number
of tokens at 𝑇 , which is impossible. Thus, 𝑇 is the inhibiting node in firing component 𝑄0
and ordinary - in firing component 𝑄1 . In accordance with aforesaid notation of multisets, the
weighted monomials are denoted by 𝑤 ⊗ 𝑀 , where 𝑤 is the weight of 𝑀 - an unweighted
monomial. The weight is skipped if 𝑤 = 1. The corresponding arrows are dashed in the figures
if 𝑤 = 𝜔. In all graphic presentations of c-e structures, nodes of unbounded capacity 𝜔, for
storing data (sets of tokens), will be drawn as bigger circles with double edge. Remaining nodes,
the "control", are of capacity 1 and drawn as smaller circles.




Figure 3: Construction of c-e structure 𝑄0 + 𝑄1 implementing "test zero". A token at the node 𝑖 starts
testing contents of 𝑇 ; on termination, the token appears at 𝑧 (zero) if 𝑇 is empty and at 𝑛 (not zero)
otherwise. The tested node 𝑇 plays two roles: inhibiting in 𝑄0 and ordinary in 𝑄1 . Capacity of 𝑇 is
infinite, whereas of remaining nodes is 1. The empty subscript/superscript 𝜃 is skipped. In the Petri net
counterpart, the inhibiting arrow enters the left transition.




  3. Basic notions of reaction systems

   This outline of reaction systems [Ehr 2007], [Ehr 2017] is limited to the primary definitions,
not their extensions, generalizations and properties established in this theory. The outline
serves only as a reference base for the next section concerned with a translation of reaction
systems into a version of cause-effect structures. That is why the original (in the literature)
denotation of certain constituents of reaction systems, has been somewhat changed, in order to
avoid naming collision with the cause-effect structures. But the new presentation is completely
equivalent to original and only tailored to the purpose of the next section. The reaction systems
will be referred to as RE. The reaction systems as well as cause-effect structures, though devised
to describe interactions or cooperation in a network of active objects, both are certain models
of computing - in the broadest meaning of this word. Reaction systems are very inspiring new
model of computing, if "computing" is to encompass interaction, not only "number crunching".
That is why a certain attempt to translate the reaction systems into c-e structures is undertaken,
though for a price of modifying semantics of the latter, but retaining their structure. There have
been also other endeavours to relate reaction systems with some formal models, for instance
[Kle 2011], [Dut 2018], [Bar 2018], [Gor 2018].

Definition 3.1 (reaction system)

A reaction system 𝐴 is created of two sets: 𝐴 = (B, R) where B is a set called a background
(intended to comprise the so-called entities), R is a set of reactions, each reaction 𝑟 ∈ R
created of three sets 𝑟 = (𝑅𝑟 , 𝐼𝑟 , 𝑃𝑟 ) where 𝑅𝑟 ⊆ B is a set of reactants, 𝐼𝑟 ⊆ B is a set
of inhibitors with 𝑅𝑟 ∩ 𝐼𝑟 = ∅ and 𝑃𝑟 ⊆ B is a set of products. The initial state of the
system 𝐴 is a set S0 ⊆ B.                                                                  □

In the literature, all the sets in Definition 3.1 are required to be finite. Though the concept of
"entity" has not been formally adopted in the definitions, for the purpose of this section it will be
understood as an object associated in a given state with an element of the background, likewise
a "token", an abstract object, of intuitive, informal status in the c-e structures or Petri nets.
Hence, the set phrase "entity present in..." in writings on the reaction systems. Since the notion
of "state" of reaction systems is analogous to that in elementary Petri nets (and elementary c-e
structures), meaning of the word "entity" may be thought of as an element of state.


Definition 3.2 (state and enabled reactions)

A state S of reaction system 𝐴 is a subset of its background: S ⊆ B. The intention is that S be
the set of those background’s members, which comprise entities. A reaction 𝑟 = (𝑅𝑟 , 𝐼𝑟 , 𝑃𝑟 )
is enabled in a state S iff 𝑅𝑟 ⊆ S and 𝐼𝑟 ∩ S = ∅.                                           □

Definition 3.3 (semantics of reaction systems - change of state)

The result of a reaction 𝑟 in a state S is the set 𝑃𝑟 if 𝑟 is enabled at S and the empty set ∅
otherwise. This result is denoted by 𝑟𝑒𝑠𝑟 (S). The result of the reaction system 𝐴 in a state S
is the union of all its reactions in this state:

                                                   ⋃︀
                                      𝑟𝑒𝑠𝐴 (S) =         𝑟𝑒𝑠𝑟 (S)
                                                   𝑟∈R

                                                                                                   □

Note that on completion (if it exists) of reaction system work, the entities in the difference of sets
S∖𝑟𝑒𝑠𝐴 (S) disappear. Note also two features differing the reaction systems from cause-effect
structures (or Petri nets): the lack of conflicts and possible absorption of reactants by products.
These features will be taken into account in definition of semantics of reaction c-e structures in
the next section.

Example 3.1 (test zero)

The "test zero" task (Fig. 3) may be realized in the reaction system 𝐴 = (B, R) with B ={𝑖, 𝑧, 𝑛, 𝑇 },
R ={𝑟1, 𝑟2} where 𝑟1 = ({𝑖}, {𝑇 }, {𝑧}), 𝑟2 = ({𝑖, 𝑇 }, ∅, {𝑛}). Result of this system’s
work depends on the initial state S0 (i.e. what the environment supplies): if S0 = {𝑖, 𝑇 }
then the result is {𝑛} ("not zero" - presence of entity at 𝑇 ), if S0 = {𝑖} then the result is {𝑧}
("zero" - absence of entity at 𝑇 ). Reactant 𝑖 initiates work of the system, while 𝑇 is tested for
presence/absence of entity. Evolution of the system 𝐴 = ({𝑖, 𝑧, 𝑛, 𝑇 }, {𝑟1, 𝑟2}) with initial
state {𝑖, 𝑇 } is the following:

  𝑟𝑒𝑠𝑟1 ({𝑖, 𝑇 }) = ∅ (because {𝑖} ⊆ {𝑖, 𝑇 } and {𝑇 } ∩ {𝑖, 𝑇 } =  ̸ ∅)
  𝑟𝑒𝑠𝑟2 ({𝑖, 𝑇 }) = {𝑛} (because {𝑖, 𝑇 } ⊆ {𝑖, 𝑇 } and ∅ ∩ {𝑖, 𝑇 } = ∅)         thus
  𝑟𝑒𝑠𝐴 ({𝑖, 𝑇 }) = 𝑟𝑒𝑠𝑟1 ({𝑖, 𝑇 }) ∪ 𝑟𝑒𝑠𝑟2 ({𝑖, 𝑇 }) = {𝑛} ("not zero")

Evolution of the system 𝐴 with initial state {𝑖} is the following:

  𝑟𝑒𝑠𝑟1 ({𝑖}) = {𝑧} (because {𝑖} ⊆ {𝑖} and {𝑇 } ∩ {𝑖} = ∅)
  𝑟𝑒𝑠𝑟2 ({𝑖}) = ∅ (because {𝑖, 𝑇 } ⊈ {𝑖} and ∅ ∩ {𝑖} = ∅)  thus
  𝑟𝑒𝑠𝐴 ({𝑖}) = 𝑟𝑒𝑠𝑟1 ({𝑖}) ∪ 𝑟𝑒𝑠𝑟2 ({𝑖}) = {𝑧} ("zero")

More complex example of evolution of a reaction system, that is its consecutive state changes,
is in section 4.

  4. Cause-effect structures working similarly to reaction systems

  The objective is to build a system structurally identical with c-e structures but working like
reaction systems. Let us call them "reaction c-e structures" and denote by RECE. The evident
counterparts of some objects in reaction c-e structures and reaction systems are the following:

  nodes←→elements of background,
  firing components←→reactions,
  causes in a firing component←→reactants in a reaction,
  effects in a firing component←→products in a reaction,
  inhibitors in a firing component←→inhibitors in a reaction,
  tokens←→entities.

The state of reaction c-e structures is a restriction of the state introduced in Definition 2.1 with
added "𝜔" to the range (codomain).

Definition 4.1 (state)

A state of reaction c-e structure 𝑈 is a total function 𝑠 : 𝑐𝑎𝑟(𝑈 ) → {0,1,𝜔}. The set of all
states of 𝑈 is denoted by S. In the following, symbols 0 and 1 will be treated as logical values
of false and true respectively and operations of propositional calculus on them will be applied.
Moreover, operations ∨, ∧ on 𝜔, are defined as: 0 ∨ 𝜔 = 𝜔 ∨ 0 = 𝜔, 0 ∧ 𝜔 = 𝜔 ∧ 0 = 0,
1 ∨ 𝜔 = 𝜔 ∨ 1 = 𝜔, 1 ∧ 𝜔 = 𝜔 ∧ 1 = 1, 𝜔 ∨ 𝜔 = 𝜔 ∧ 𝜔 = 𝜔, ¬𝜔 = 0. As formerly, 𝜔 will be
used for inhibiting actions. Interpretation of 0 and 1 as false and true is justified by absorption
property of entities in reaction systems and will be made formal in Definition 4.6.               □

The lack of conflicts requires introducing for reaction c-e structures concept called here "volley",
to differ it from "salvo" for c-e structures introduced in Definition 1.5.

Definition 4.2 (weights of monomials and inconsistent firing components)

Given a c-e structure 𝑈 = ⟨𝐶, 𝐸⟩ and its firing component 𝑄 ∈FC[𝑈 ], let along with the
pre-set ∙ 𝑄 and post-set 𝑄∙ of 𝑄, some functions
 ∙ 𝑄: ∙ 𝑄 → {0,1,𝜔} and 𝑄∙ : 𝑄∙ → {0,1,𝜔} be given as additional information. The value
∙ 𝑄(𝑥) is called a weight of monomial 𝐸 (𝑥) and the value 𝑄∙ (𝑥) - a weight of monomial
                                            𝑄
𝐶𝑄 (𝑥). For 𝐸𝑄 (𝑥) = 𝜃 or 𝐶𝑄 (𝑥) = 𝜃 assume respectively ∙ 𝑄(𝑥) = 0 or 𝑄∙ (𝑥) = 0.
Additionally, ∙ 𝑄(𝑥) = 0 for 𝑥 ∈    / ∙ 𝑄 and 𝑄∙ (𝑥) = 0 for 𝑥 ∈      / 𝑄∙ . As formerly, 𝜔 is
interpreted as a "disable signal" and used for defining inhibiting nodes. Firing components 𝑄
and 𝑃 are inconsistent if for a certain 𝑥 ∈ ∙ 𝑄∙ ∩ ∙ 𝑃 ∙ , weights ∙ 𝑄(𝑥) and ∙ 𝑃 (𝑥) or 𝑄∙ (𝑥)
and 𝑃 ∙ (𝑥) are different: ∙ 𝑄(𝑥) ̸= ∙ 𝑃 (𝑥) or 𝑄∙ (𝑥) ̸= 𝑃 ∙ (𝑥). Note that detached 𝑄 and 𝑃
(Definition 1.5) are not inconsistent.                                                       □

Remark. Inconsistency of firing components must be avoided so that to obtain free of conflicts
behaviour of the reaction c-e structures. The inconsistency is exemplified by the following c-e
structure: 𝑈 = {𝑥0⊗𝑦+𝑧 , 𝑦 𝑥 , 𝑧 𝑥 } containing two firing components: 𝑄 = {𝑥0⊗𝑦 , 𝑦 𝑥 }, 𝑃 =
{𝑥𝑧 𝑧 𝑥 }, thus ∙ 𝑄(𝑥) = 0, ∙ 𝑃 (𝑥) = 1. In the initial state 𝑠 with 𝑠(𝑥) = 1, 𝑠(𝑦) = 𝑠(𝑧) = 0
the parallel execution of the set of firing components 𝐺 = {𝑄, 𝑃 } yields undetermined
state of node 𝑥: it might be either 1 or 0. 𝑈 is a direct translation of the reaction system
({𝑥, 𝑦, 𝑧}, {𝑄, 𝑃 }, {𝑥}) with 𝑄 = ({𝑥}, ∅, {𝑥, 𝑦}), 𝑃 = ({𝑥}, ∅, {𝑧}), which performs
state transformation {𝑥} → {𝑥, 𝑦, 𝑧}. The same transformation of state is performed by the
reaction c-e structure 𝑉 = {𝑥0⊗𝑦+0⊗𝑧 , 𝑦 𝑥 , 𝑧 𝑥 }, leading to 𝑡(𝑥) = 𝑡(𝑦) = 𝑡(𝑧) = 1.

Definition 4.3 (volley - simultaneous firing, family FCV, extension of weight functions)

Any set 𝐺 ⊆FC without inconsistent firing components is called their volley. The family of
volleys is denoted by FCV. So, if 𝐺 ⊆FC[𝑈 ] then FCV [𝑈 ] ⊆ 2FC[𝑈 ] for a c-e structure 𝑈 ,
denotes a collection of volleys in 𝑈 . The pre-set ∙ 𝐺 and post-set 𝐺∙ of a volley 𝐺 are defined as
in Definition 1.4. Extension of the weight functions ∙ 𝑄 and 𝑄∙ onto the volley 𝐺 are defined
as follows:
             ∙ 𝑄(𝑥)    for arbitrary 𝑄 if it belongs to 𝐺
          {︂
∙ 𝐺(𝑥) =
             0         else

                𝑄∙ (𝑥)   for arbitrary 𝑄 if it belongs to 𝐺
           {︂
𝐺∙ (𝑥) =
                0        else
This is a correct definition, since for any firing components 𝑄 and 𝑃 in 𝐺: ∙ 𝑄(𝑥) = ∙ 𝑃 (𝑥) if
𝑥 ∈ ∙ 𝐺 and 𝑄∙ (𝑥) = 𝑃 ∙ (𝑥) if 𝑥 ∈ 𝐺∙ . Functions ∙ 𝐺 and 𝐺∙ will be used in definition of
reaction c-e structures semantics.                                                           □

Definition 4.4 (inhibitors)

As in Definition 2.3, for a firing component 𝑄 ∈FC[𝑈 ], the set 𝑖𝑛ℎ[𝑄] = {𝑥 ∈ ∙ 𝑄 : ∙ 𝑄(𝑥) =
𝜔} comprises all nodes in the pre-set of 𝑄, whose effect monomials 𝐸𝑄 (𝑥) are of weight 𝜔.
This also extends onto the volleys: 𝑖𝑛ℎ[𝐺] = {𝑥 ∈ ∙ 𝐺 : ∙ 𝐺(𝑥) = 𝜔} where 𝐺 ∈FCV [𝑈 ]. □

Definition 4.5 (enabled firing components and enabled volleys)

For a firing component 𝑄 ∈ FC[𝑈 ] and state 𝑠 let the formula 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝑄](s) be defined as:

∀𝑥 ∈ 𝑖𝑛ℎ[𝑄] : 𝑠(𝑥) = 0 ∧ ∀𝑥 ∈ ∙ 𝑄∖𝑖𝑛ℎ[𝑄] : 𝑠(𝑥) = 1

For a volley 𝐺 ∈FCV [𝑈 ], the formula 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝐺](𝑠) is defined as above by replacing 𝑄 with
𝐺 and FC[𝑈 ] with FCV [𝑈 ].

In the "token game" metaphor, 𝑄 (or 𝐺) is enabled in the state 𝑠 iff none of inhibiting nodes
𝑥 ∈ ∙ 𝑄 (or 𝑥 ∈ ∙ 𝐺) contains a token and each remaining node contains. As formerly, the
inhibiting nodes will be called inhibitors.                                                □

Definition 4.6 (semantics [[ ]] of reaction c-e structures)

For a volley 𝐺 ∈FCV [𝑈 ], 𝐺 ̸= ∅ let [[𝐺]] ⊆ S × S be a binary relation defined as:
(𝑠, 𝑡) ∈ [[𝐺]] iff 𝑒𝑛𝑎𝑏𝑙𝑒𝑑[𝐺](𝑠) ∧ ∀𝑥 ∈ 𝑐𝑎𝑟(𝑈 ) : 𝑡(𝑥) = (𝑠(𝑥) ∧ ¬∙ 𝐺(𝑥))⋃︀∨ 𝐺∙ (𝑥)
(say: 𝐺 transforms state 𝑠 into 𝑡). Semantics [[𝑈 ]] of 𝑈 ∈RECE is            [[𝐺]], for any
                                                                         𝐺∈FCV [𝑈 ]
maximal volley 𝐺, i.e. if 𝐺 ⊆ 𝐺′ ∈FCV [𝑈 ] and
(𝑠, 𝑡) ∈ [[𝐺′ ]] then 𝐺 = 𝐺′ . Closure [[𝑈 ]]* and reachability and computation are defined as
in Definition 1.7.                                                                          □


In Definition 4.6, if 𝑥 ∈ ∙ 𝐺 then ∙ 𝐺(𝑥) ̸= 𝜔, because the volley 𝐺 is enabled in the state 𝑠
thus ∙ 𝐺(𝑥) is 0 or 1. If 𝑥 ∈
                            / ∙ 𝐺∙ then ∙ 𝐺(𝑥) = 0 and 𝐺∙ (𝑥) = 0 hence ¬∙ 𝐺(𝑥) = 1, thus
𝑡(𝑥) = 𝑠(𝑥) (strictly, "=" means equivalence). Evidently, formula (𝑠(𝑥) ∧ ¬∙ 𝐺(𝑥)) ∨ 𝐺∙ (𝑥)
is equivalent to (𝑠(𝑥) ⇒ ∙ 𝐺(𝑥)) ⇒ 𝐺∙ (𝑥). Note also that description of semantics by means
of this propositional formula is justified by the property of reaction systems: presence of token
("entity") at a node absorbs another token arriving in this node. Another property of reaction
systems, the lack of conflicts between different reactions, takes place in reaction c-e structures
due to the lack of inconsistent firing components in 𝐺 ∈FCV [𝑈 ].

  Example 4.1 (reaction c-e structure assembling a chemical molecule)
A description of creating some chemical molecules presents the reaction system

                  𝐴 = ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌, 𝑍}, {𝑟1, 𝑟2, 𝑟3, 𝑟4, 𝑟5, 𝑟6}),

starting with initial state {𝐶, 𝐻, 𝑂} and with reactions defined as follows:

𝑟1 = ({𝐶, 𝐻}, ∅, {𝑈 })         𝑈 contains molecule 𝐶𝐻      (methylidyne)
𝑟2 = ({𝑈, 𝐶, 𝐻}, ∅, {𝑉 })      𝑉 contains molecule 𝐶2 𝐻2     (acetylene)
𝑟3 = ({𝑉, 𝐻}, ∅, {𝑊 })         𝑊 contains molecule 𝐶2 𝐻3    (ethylenyl)
𝑟4 = ({𝑊, 𝐻}, ∅, {𝑋})          𝑋 contains molecule 𝐶2 𝐻4     (ethylene)
𝑟5 = ({𝑋, 𝐻, 𝑂}, ∅, {𝑌 })       𝑌 contains molecule 𝐶2 𝐻5 𝑂 (ethoxide)
𝑟6 = ({𝑌, 𝐻}, ∅, {𝑍})          𝑍 contains molecule 𝐶2 𝐻5 𝑂𝐻 (ethanol)

A diagram of the final result, that is the ethanol molecule, is in Fig. 4 and a certain translation
of this reaction system into a reaction c-e structure is depicted in Fig. 5. Successive steps of the
reaction system evolution are the following:


𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂}) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂} and ∅ ∩ {𝐶, 𝐻, 𝑂} = ∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂}) = 𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂}) = 𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑂}) = 𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂}) =
𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂}) = ∅ thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂}) = {𝑈 }

𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂, 𝑈 }) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂, 𝑈 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈 } = ∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂, 𝑈 }) = {𝑉 } (since {𝐶, 𝐻, 𝑈 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈 } = ∅)
𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂, 𝑈 }) = 𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑈 }) = 𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂, 𝑈 }) =
𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂, 𝑈 }) = ∅     thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂, 𝑈 }) = {𝑈, 𝑉 }

𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } = ∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = {𝑉 } (since {𝐶, 𝐻, 𝑈 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } = ∅)
𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = {𝑊 } (since {𝐻, 𝑉 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉 } = ∅)
𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = 𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = 𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = ∅ thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉 }) = {𝑈, 𝑉, 𝑊 }

𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } and ∅∩{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } =
∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = {𝑉 }      (since {𝐶, 𝐻, 𝑈 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } = ∅)
𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = {𝑊 } (since {𝐻, 𝑉 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } and ∅∩{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } =
∅)
𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = {𝑋} (since {𝐻, 𝑊 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } and ∅∩{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 } =
∅)
𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = 𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = ∅ thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊 }) = {𝑈, 𝑉, 𝑊, 𝑋}

𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} = ∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑉 } (since {𝐶, 𝐻, 𝑈 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} = ∅)
𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑊 } (since {𝐻, 𝑉 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} = ∅)
𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑋} (since {𝐻, 𝑊 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} = ∅)
𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑌 } (since {𝐻, 𝑂, 𝑋} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋} = ∅)
𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = ∅) thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋}) = {𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }

𝑟𝑒𝑠𝑟1 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑈 } (since {𝐶, 𝐻} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅)
𝑟𝑒𝑠𝑟2 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑉 } (since {𝐶, 𝐻, 𝑈 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅)
𝑟𝑒𝑠𝑟3 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑊 } (since {𝐻, 𝑉 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and ∅ ∩
{𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅)
𝑟𝑒𝑠𝑟4 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑋} (since {𝐻, 𝑊 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅)
𝑟𝑒𝑠𝑟5 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑌 } (since {𝐻, 𝑂, 𝑋} ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅)
𝑟𝑒𝑠𝑟6 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑍} (since {𝐻, 𝑌 } ⊆ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } and
∅ ∩ {𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 } = ∅) thus
𝑟𝑒𝑠𝐴 ({𝐶, 𝐻, 𝑂, 𝑈, 𝑉, 𝑊, 𝑋, 𝑌 }) = {𝑈, 𝑉, 𝑊, 𝑋, 𝑌, 𝑍}




Figure 4: Diagram of ethanol. C, H, O - symbols of Carbon, Hydrogen and Oxygen atoms.
Figure 5: A c-e structure with initial state 𝑠(𝐶) = 𝑠(𝐻) = 𝑠(𝑂) = 1 (and empty remaining nodes)
imitating behaviour of reaction system 𝐴 specified in Example 4.1. Regarding it as a translation of 𝐴,
note that nodes 𝑐1, 𝑐2, ℎ1, ℎ2, ℎ3, ℎ4, ℎ5, ℎ6 are some "artifacts" of this fairly liberal translation and
have no counterparts in 𝐴. Intuitively, they might be seen as holding single atoms of elements 𝐶 and
𝐻.



  References

[Bar 2018] Barbutti R., Bove P., Gori R., Levi F., Milazzo P., Simulating Gene Regulatory Networks
using Reaction Systems, Proceedings of Concurrency, Specification and Programming 2018, pp.
119-132

[Cza 2019] Czaja L. Cause-Effect Structures. An Algebra of Nets with Examples of Application,
Lecture Notes in Networks and Systems 45, Springer 2019

[Dut 2018] Dutta S., Jankowski A., Rozenberg G., Skowron A., Linking Reaction Systems with
Rough Sets. Fundamenta Informaticae 165(3-4): 283-302 (2019)

[Ehr 2007] Ehrenfeucht A., Rozenberg G.: Reaction systems. Fundamenta Informaticae 75 (2007),
pp. 263-280

[Ehr 2017] Ehrenfeucht A, Petre I., Rozenberg G., Reaction Systems: A Model of Computation
Inspired by the Functioning of the Living Cell, in: The Role of Theory in Computer Science, Essays
Dedicated to Janusz Brzozowski, edited by Stavros Konstantinidis, Nelma Moreira, Rogério Reis
and Jeffrey Shallit, World Scientific 2017, pp.1-32

[Gor 2018] Gori R., Gruska D., Milazzo P., Hidden States in Reaction Systems, Proceedings of
Concurrency, Specification and Programming 2018, pp. 133-144
[Kle 2011] Kleijn J., Kountny M., Rozenberg G., Modelling Reaction Systems with Petri Nets, in:
Proc. of the International Workshop on Biological Processes & Petri Nets (BioPPN 2011), pp.
36–52