How it works

Rewriting where the neighbourhood relation is part of the data. A collection is not just a bag - it can be a sequence, a grid, a graph, or a group-based field - and a rule matches a *path of neighbouring* elements and substitutes for it. One formalism therefore covers sorting a sequence, a cellular automaton on a lattice, and restriction-enzyme cuts on a string, differing only in which topology the collection carries. Useful to Chemart as a way of thinking about space abstractly.

S

a topological collection: values organised by a neighbourhood relation. Monoidal collections (set, bag: every element neighbours every other; seq: the right neighbour), group-based data fields (grid <north, east>, hexagon <east, north, northeast; east + north = northeast>) whose positions exist a priori and may be <undef>, and nested collections (a TUBE bag of DNA sequences). Species are values (set, bag), whole strands (tube) or position-qualified values value@position (seq, grid, hexagon: 3@2, true@1_4, undef@0_0) · implicit

R

trans T = { pattern / guard => replacement; ... }: a rule selects a path of neighbouring elements matching the pattern (x, y: y neighbours x; x |d> y: y is the d-neighbour of x; X+: a non-empty subsequence) whose guard holds, and substitutes the replacement for it. Book: x, y / x > y => y, x sorts a sequence · arity variable

A

graph-rewrite, maximally-parallel · none

Parameters

What to look for

• book 9.6 and Cohen 2003: x, y / x > y => y, x iterated to its fixpoint sorts a sequence; in the network the sorted configuration is inert
• book 9.6 and Giavitto & Michel 2002 sec. 3.1: EcoRI cuts CCCGAATTCAA into CCCG and AATTCAA; React[fixpoint] on the tube CCCGAATTCAA, TTGAATTCGGG returns AATTCAA, TTG, CCCG, AATTCGGG
• Cohen 2003: x, y/(y mod x = 0) => [x] iterated on the set 2..n leaves the primes up to n
• Giavitto & Michel 2002 sec. 3.2: Eden growth x, <undef> / x => x, true spreads from one cell; the same transformation runs on grid and hexagon
• Giavitto & Michel 2002 fig. 2: Turn rotates a five-cell cross by 90 degrees per step
• Cohen 2003 fig. 4: bead-sort lets beads fall along north, sorting rows 3, 2, 4, 2 into 2, 2, 3, 4
• Giavitto et al. 2011: MGS also models flocking (Delaunay neighbourhoods) and epithelial growth (not implemented)

Implementation decisions

• The book's primary reference [320] (ENTCS 59(4), 2001) could not be read: ScienceDirect refuses automated downloads and the Wayback Machine and the MGS site (mgs.spatial-computing.org, certificate for lacl.fr only) were unreachable. The language was reconstructed from the 2002 UMC paper by the same authors, which restates it, Cohen 2003 and the 2011 SCS paper. The Fundamenta Informaticae 2002 and BioSystems 2003 [321] papers were not obtained either; Anabaena and cAMP models are not offered.
• Scope: set, bag, seq, the GBFs grid <north, east> and hexagon <east, north, northeast; east + north = northeast>, and tube (a bag of sequences, the only nesting needed by the published programs). Maps/records, free-group GBFs (trees), Delaunay and cellular-complex collections, rule attributes (probabilities, non-consuming rules), sub-collection patterns on sets ((x / x < 3)+ as S) and user-defined functions are not implemented.
• Pattern language: variables, integer/string/boolean literals, <undef>, ',' and |d> (d any signed sum of generators, as in Turn's |Y-X>), per-element guards x/guard (all guards are conjoined and evaluated with every variable bound, which is equivalent because guards have no side effects) and X+, X*, x+ as X on tube strands. Guards and replacements use a small expression language (or, and, not, =, ==, !=, <, <=, >, >=, +, -, *, mod, div, size) parsed by Chemart, never Python eval. Replacements accept the book form y, x, Cohen's [x] and y::x::empty_seq (Cohen prints 'empty seq'), and () for nothing.
• Positional collections: species are value@position and a replacement must have as many elements as the pattern (for GBFs this is the language's rule; Cohen 2003 sec. 3). Leibnizian length changes on seq (x => x, x) are not offered because they renumber positions; strand rewriting with length changes is available in a tube. <undef> is a species per site (undef@r_c) so that growth into an empty site is a reaction. Grids are finite windows of the infinite GBF (bounded or torus): the published figures show only part of the infinite domain.
• Tube rules match whole strands: the published program applies Restriction to a DNA string and keeps hd of the result, a TUBE holding the whole cut strand, so X+ and Y+ must cover the strand; strands with several recognition sites give one reaction per cut. A strand id is its atoms joined (CCCG) when all are single characters, otherwise (atom,atom).
• Priorities: a lower-priority rule is not applied to a sub-collection (same positions and values, or same strand) that a higher-priority rule matches; this is exact for Void after EcoRI and for default rules x => [x]. Elastic rewritings (replacement equal to the match) produce no reaction and are skipped in runs.
• Closure semantics: species-level closure like chemart.expand (every rule on every tuple of known species lying on a path of the topology); a reaction may therefore combine site values that never coexist in a single run. Sets are treated as bags whose replacement is deduplicated; the union with an equal value already present elsewhere cannot be expressed as stoichiometry.
• Runs: the MGS default T[iter=fixpoint] with the maximal-parallel strategy (Cohen 2003 sec. 2; SCS 2011 sec. 4.1) or an asynchronous alternative, stopped when no rule changes the collection or after 10000 steps (Turn never reaches a fixpoint). The run is recorded in extras.run and does not change the network; the stochastic Gillespie strategy of MGS is not offered because no rates are published.
• Default inputs the sources do not give: the book's sort has no input ([4, 2, 5, 1, 3] is used); the sieve runs on 2..30 (Cohen: 'the integers between 2 and n'); Eden starts from one true cell in the middle of a 7x7 grid. The restriction-enzymes strands, the bead rows 3, 2, 4, 2 and the Turn cross are the published ones.
• v1 parameters collection_type (enum) and transformations (callable) became collection plus program/rules. The v1 provides tag compartments was dropped: the only nesting implemented is a tube of strands, not membranes. 'catalysts' comes from rules that keep a matched element (sieve x + y -> x, Eden).
• No kinetics: MGS transformations have no rates, so reactions carry no rate law.

Sources

• Banzhaf, W. & Yamamoto, L. (2015). Artificial Chemistries, section 9.6 (topological collections; trans sort = { x, y / x > y => y, x }; the EcoRI rule and its cut of CCCGAATTCAA into CCCG and AATTCAA) and 18.3.2 (one paragraph on the biological models of [321]).
• Giavitto, J.-L. & Michel, O. (2002). Data structure as topological spaces. Unconventional Models of Computation (UMC 2002), LNCS 2509:137-150. Collection types and neighbourhoods (sec. 2.1: set, bag, seq, GBF Grid2 and Hexagon), the path pattern grammar (sec. 2.2), substitution, Newtonian and Leibnizian collections and the iteration options (sec. 2.3), the restriction enzymes program with its published input and result (sec. 3.1), the Eden model on grid and hexagon (sec. 3.2, fig. 1) and the Turn transformation (fig. 2). http://repmus.ircam.fr/_media/giavitto/export/giavitto__umc02__data_structure_as_topological_spaces.pdf
• Cohen, J. (2003). Typing rule-based transformations over topological collections. RULE 2003, ENTCS 86(2). Rule application semantics (sec. 2: rules in order, each on a maximal set of non-intersecting occurrences), the bubble sort and the Eratosthenes sieve on a set (sec. 2.1), the default rule x => [x] (sec. 4.1), the bead-sort on a grid (sec. 5.2, fig. 4) and the strategies (sec. 5.3). https://arxiv.org/abs/0912.4877
• Giavitto, J.-L., Michel, O. & Spicher, A. (2011). Interaction based simulation of dynamical system with a dynamical structure (DS)2 in MGS. SCS 2011. Guards, the linearity of patterns, the maximal-parallel and Gillespie strategies, rule priorities by declaration order, Delaunay collections. http://repmus.ircam.fr/_media/giavitto/export/giavitto_scs2011.pdf

Banzhaf & Yamamoto, Artificial Chemistries (2015), §9.6; biology 18.3.2

Preview at default parameters

21 species · 25 reactions · status complete · seed 1

4@0 + 2@1 -> 2@0 + 4@1
5@2 + 1@3 -> 1@2 + 5@3
4@1 + 1@2 -> 1@1 + 4@2
2@1 + 1@2 -> 1@1 + 2@2
5@3 + 3@4 -> 3@3 + 5@4
4@0 + 1@1 -> 1@0 + 4@1
2@0 + 1@1 -> 1@0 + 2@1
4@1 + 2@2 -> 2@1 + 4@2
4@2 + 1@3 -> 1@2 + 4@3
4@2 + 3@3 -> 3@2 + 4@3
2@2 + 1@3 -> 1@2 + 2@3
5@2 + 3@3 -> 3@2 + 5@3
4@1 + 3@2 -> 3@1 + 4@2
3@2 + 1@3 -> 1@2 + 3@3
3@2 + 2@3 -> 2@2 + 3@3
5@2 + 4@3 -> 4@2 + 5@3
5@2 + 2@3 -> 2@2 + 5@3
4@2 + 2@3 -> 2@2 + 4@3
4@3 + 3@4 -> 3@3 + 4@4
4@0 + 3@1 -> 3@0 + 4@1
3@1 + 1@2 -> 1@1 + 3@2
3@1 + 2@2 -> 2@1 + 3@2
5@3 + 4@4 -> 4@3 + 5@4
3@0 + 2@1 -> 2@0 + 3@1
3@0 + 1@1 -> 1@0 + 3@1

Generated by the uploader with chemart push; the hub never runs uploaded code.