Wolfram Cloud Document

ΔSys: String and Term Rewriting for Simplex Category’s Morphisms with code (2)

(β3.0)

Dara O Shayda
dara@compclassnotes.com
July 21st 2025

In[]:=

DateObject[]

Out[]=

Mon 21 Jul 2025 18:19:39GMT+1

Abstract

This is the third version (β3.0) of the previous publication with the same title. In this new version a sample coded Δ Rewriting system is provided to implement non-deterministic asynchronous parallel String Rewriting Systems (ΔSys) with a variety of helper functions and graphics. ΔSys takes as input a morphism in Simplex Category Δ and returns a list of compositions of the morphisms

and

as an expansion (generators). Each run of the ΔSys can be recreated by means of a preassigned Seed Random [8]. The new coded String Rewriting system is equipped with modules that are parametric symbols taking arguments. The code is also equipped with push/pop stacks (scope/function call-stacks).

Live Code Notebook:https://www.wolframcloud.com/obj/ccn2/Published/term_Rewrite_morph_v2.nb  In case of bugs in the code or the theory please make contact to fix ASAP.

Previous version DOI: 10.13140/RG.2.2.22364.81280

Keywords: Category Theory, Universal Properties, Term Rewriting, String Rewriting, Kolmogorov Complexity, Simplex Category, Processorial Calculi, Serialization, Reversibility, Quantitative Category theory.

100% Fat Free Mathematics

Software

Release: β3.0

Scripts: Symbolic computations performed in Wolfram Mathematica 14.2 .Notebook: https://www.wolframcloud.com/obj/ccn2/Published/term_Rewrite_morph_v2.nb Support: Contact the author for additional code, bugs, correction in maths and algebraic/mathematical mistakes or invalid inferences.Nomenclature: Most functions and most identifiers start with lower case letters, all native vendor identifiers start with upper case. No Packaging: There is no software engineering applied to the code here nor elsewhere in the author’s technical notes to reduce the difficulties and version mismatches in future. The eager readers can simply copy paste the code or download and run the notebook. TODO: 1. Monoidal product of morphisms2. Replace the {n,m}X by X(n,m) as a module similar to j() 3. Develop code for the Arrow Category of Δ or Arr(Δ) 4. Grammarian upgrade for Free Free Foram Programming Language to support both Δ and Arr(Δ) 5. Parallelize amongst multiple physical hardware CPUs6. Add Petri Net asynchronous clocks to model the asynchronism  Known Issues:1. Not all returned compositions of the generators

σ,δ

reconstruct the original morphism; or the Rewriting system requires much longer running times. We still suspect a sneaky bug somewhere!TOLEARN:1. Monoidal structure on both Δ and Arr(Δ) 2. Rewriting system for the Arr(Δ) © 2012-Present CCN StudiosCreative Commons Attribution-NonCommercial-ShareAlike 4.0

1. Simplex Category

Definition 1.1: Simplex Category Δ of Finite Ordered Sets [1,2]● objects

[0],[1],[2]

, … with

[n]={0,1,2,…,n}

and● morphism

[n]→[m]

is a nondecreasing map

{0,1,2,…,n}→{0,1,2,…,m}

between the corresponding sets.● Here nondecreasing for a map

φ:[n]→[m]

means by definition that

φ(i)≥φ(j)⟸i≥j

. In other words, Δ is a Small category [2] equivalent to nonempty finite totally ordered sets and nondecreasing maps. There are exactly n+1 morphisms

[0]→[n]

and there is exactly 1 morphism

[n]→[0]

. There are exactly (n+1)(n+2)/2 morphisms

[1]→[n]

and there are exactly n+2 morphisms

[n]→[1]

. And so on and so forth.Definition 1.2 : For any integer

n≥1

, and any

0≤j≤n

we let

:[n-1]→[n]

denote the injective order preserving map skipping j. For any integer

n≥0

, and any

0≤j≤n

we denote

:[n+1]→[n]

the surjective order preserving map with

-1





({j})={j,j+1}

.Lemma 1.3: Any morphism in Δ can be written as a composition of the morphisms

and

(generators).Proof. Let φ :[n]→[m] be a morphism of Δ. If

j∉Im(φ)

, then we can Rewrite:

∘ψ

(1.3.1)for some morphism

ψ:[n]→[m−1].

φ(j)=φ(j+1)

then we can Rewrite:

ψ∘

n-1

(1.3.2)or some morphism

ψ:[n−1]→[m]

. The result follows because each replacement as above lowers n+m and hence at some point φ is both injective and surjective, hence an identity morphism.  (1.3.1) and (1.3.2) constitute the bulk of the String Rewriting algorithm below.

2. Rewriting Δ Morphism

In mathematics, computer science, and logic, Rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects. [3]

Rewriting can be non-deterministic and asynchronous. A single rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications i.e. replacement.

Of importance to this research are three such Rewriting systems:

1. Term Rewriting: A term rewriting system (TRS) is a rewriting system whose objects are terms(e.g. Logic, arithmetic), which are expressions with nested sub-expressions

2. String Rewriting: Simple rule based String replacement regardless of any additional data attached to the Strings

3. String Term Rewriting: A medley of both which does suit the purse of this research

2.1 String Rewriting Δ Morphism

Definition 2.1: String Term Rewriting, coined as the ΔSys, as a Serializer, is quite simple and inspired by the proof of Lemma 1.3 namely (1.3.1) and (1.3.2) :

Tape⟶[{n,m}X],φ[{0,0}X]⟶""[{n,m}X]⟶Y[{n,m-1}X][{n,m}X]⟶[{n-1,m}X]ZY⟶({m-1,m},δ,j(1))Z⟶({n,n-1},σ,j(2))Tape⟶∏σδ==φ⟶Termination

(2.1)

Y≡

:[n-1]→[n]

(skip j)

Z≡

:[n+1]→[n]

-1





({j})={j,j+1}

⟶ : String substitution

j(1),j(2)

: Symbol/token j in j()-form is called a Module namely a parametric symbol/token which combines with a parameter list grouped between brackets of some kind. In this case the two js access their values from two different sources of data namely image of

and pre-image of

. [6,7]Remark:

{n,m}X

could have been defined as

X(n,m)

namely as a Module. TODO: we will update to experiment with in the next release. [: Push stack: start of a new scope to create and contain a morphism ]: Pop stack: end of the the scope and morphism formation ended{: start of list of data elements}: end of the list(: start of a fully formed morphism

): end of the morphisms ,: separator == : Boolean conditionalFlattening the two dimensional mathematical operator fonts, as such Y and Z are replaced by

({m-1,m},δ,j(1)),({n,n-1},σ,j(2))

thus denoted by

and

n-1

namely the serialized transforms of

and

n-1

≡({m-1,m},δ,j)

n-1

≡({n,n-1},σ,j)

We say this String Term Rewriting system can Rewrite a morphism or serializes a morphism. With any further ado we can now claim: Theorem 2.3 : ΔSys the Term Rewriting Serializer can serialize every morphism in Δ category with

and

n-1

forming the String Rewrite rules (2.1).

3.0 ΔSys

3.1 Software Guide

3.1.1 Initialize ΔSys

Simply run the expression/script cell below and a fresh new ΔSys programming environment with appropriate notations and operators and functions and grammars.

Remark: Sufferin’ succotash is a humorous exclamation, often used as a mild curse or a way to express surprise, frustration, or annoyance, particularly in place of stronger language. It’s famously associated with Sylvester the Cat from Looney Tunes, who uses the phrase due to his lisp. The phrase is a euphemism, replacing “Suffering Savior” to avoid blasphemy, and originated during the Victorian era.

Function call

3.1.2 φ format

3.1.3 Overview

As you can see the loop is placed in the Hold[ ] vault and not evaluated.

If & when required the function ReleaseHold[ ] evaluates the contents of the Hold vault:

3.1.5 Seed

Take the seed from the previous example and assign it to the seed in the same code and as you can see all the random structures are preserved and therefore repeated just the same.

3.2 Support functions

3.2.1 σδ[n, m]

3.2.2 σδ[n, m,k]

3.2.3 toφ [ ]

-1 indicates error or invalid composition.

3.2.3 morphismG[ ]

3.2.4 arrowHeadsSize

Global variable arrowHeadsSize is by default set to 0.04:

Increase or decrease the arrowHeadsSize to fit better arrow heads of proper size:

4. Rewriting examples

First synthesize a sample random morphism or by any other means:

Next run the setup and call to ΔSys[ ] to configure and invoke the Rewriting system:

4.1 Example

4.2 Example

4.3 Example

4.4 Example

4.5 Example

This may take a few minutes of might require increasing the outTries!

References

[1] The category of finite ordered sets
https://stacks.math.columbia.edu/tag/0164

[2] Small Category
https://ncatlab.org/nlab/show/small+category

[3] Rewriting
https://en.wikipedia.org/wiki/Rewriting#Term_rewriting_systems

[4] Universal Property
https://en.wikipedia.org/wiki/Universal_property

[5] Process Calculi
https://en.wikipedia.org/wiki/Process_calculus

[6] https://en.wikipedia.org/wiki/L-system#Parametric_grammars

[7] https://en.wikipedia.org/wiki/Image_(mathematics)

[8] https://en.wikipedia.org/wiki/Random_seed