gcrsim

Graph Controlled string Rewriting SIMulator. It simulates the derivation of regulated rewriting systems, in particular insertion-deletion systems with graph control: components (states) hold sets of strings, rules rewrite a string in one component and send the result to another one, and the simulator advances all components synchronously, step by step.

Main features

• Simulation of many variants of regulated rewriting and of insertion-deletion systems. Graph-controlled, matrix, programmed, time-varying, random-context and ordered grammars, Marcus contextual grammars, evolutionary processors, networks of processors and insertion-deletion systems are all written with the same few rule forms (see docs/grammar-types.md).
• Catching wrong derivations and the stage where they happen. Marks flag the strings you care about, for example every terminal string that is not in the language you intended, at the step and component where they appear. The traceback then prints the full derivation, rule by rule from the axiom, of any marked string or of any string you name (see docs/marks-and-derivations.md).

gcrsim is a complete rewrite, in Python, of the earlier Perl simulator of the same name, and its evolution: the model language is new, the semantics are written down and checked against an independent reference interpreter, and it adds marks, derivation sequences and resource limits. The Perl version is kept at github.com/sverlan/gcrsim-perl; models written for it are migrated with gcrsim-convert, see docs/migration.md.

• a small package, standard library only, Python 3.11+;
• rule forms ins, del, sub, plain rules, send() and regular-expression rules, permitting / forbidding words, multi-character symbols and symbol classes, UTF-8;
• for the part of the language without regular expressions, a written specification, an independent reference interpreter, differential tests and --cross-check (see docs/checking.md);
• for long experiments: declarative component conditions, resource limits, progress reporting, csv and jsonl output.

Installation

Python 3.11 or later; there are no other dependencies. The package installs three programs: gcrsim (the simulator), gcrsim-convert (migration of Perl-era models) and gcrsim-retention (look into a retention file).

pip install gcrsim                    # into the current environment
pipx install gcrsim                   # as an isolated command-line tool
uv tool install gcrsim                # the same, with uv
uvx gcrsim model.txt 10               # run the simulator once, without installing

Running

gcrsim model.txt [steps]
python -m gcrsim model.txt [steps]      # the same, from a checkout of the repository without installing

With steps (on the command line or in the configuration) the simulator runs that many steps and exits; with -i it waits for a command after each step (Enter for the next step, q to quit, more commands in docs/interactive.md).

A first model

A matrix grammar for aⁿbⁿcⁿ, a language that needs several components. A matrix is a chain of rules applied one after the other, so each rule gets its own component; the first rules of all the matrices are in component 1, and the last rule of m2 returns to it:

# matrix m1 = (S -> ABC), m2 = (A -> aA, B -> bB, C -> cC), m3 = (A -> a, B -> b, C -> c)
[axioms]
1 = ["S"]

[rules.1]
# m1 (one rule), and the first rules of m2 and m3
S -> A B C, 1
A -> a A, 2
A -> a, 4
# m2: B -> bB in component 2, C -> cC in component 3, then back to component 1
[rules.2]
B -> b B, 3
[rules.3]
C -> c C, 1
# m3: B -> b in component 4, C -> c in component 5, and the word is in component 6
[rules.4]
B -> b, 5
[rules.5]
C -> c, 6

The model is the file examples/cookbook/08_matrix_direct.txt; gcrsim examples/cookbook/08_matrix_direct.txt 12 prints, at every step, the strings of each component; abc, aabbcc, ... appear in component 6.

Documentation

Supported grammars

A summary; the full table, with one sentence on how each grammar is written, is in docs/grammar-types.md, and docs/grammars.md gives an example of each in the classical notation and as a model.

How it is developed

The development is AI-assisted, and the work is shared between the human author and the AI. The plan is discussed and validated by the human author. The AI implements the code and writes the tests; the human rereads the code. The examples are written by the AI and the human together, and the results are verified by the human. Independent AI reviews of the plan and of the code were used as an additional check; they do not replace the human steps. What the automatic checks do and do not guarantee is described in docs/checking.md.

Development

uv run pytest                 # fast tests, plus the Perl comparisons when perl is on PATH

The Perl comparison tests use the original models and configurations in tests/fixtures/perl.