$$\gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\rarrbar{ {\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{ { {\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\rawsymbol#1{\operatorname{#1}} \gdef\colorsymbol#1#2{\textcolor{#1}{\rawsymbol{#2}}} \gdef\lsymbol#1{\colorsymbol{262626}{#1}} \gdef\msymbol#1{\colorsymbol{b50800}{#1}} \gdef\osymbol#1{\colorsymbol{00427f}{#1}} \gdef\lstring#1{\textcolor{666666}{\textrm{\textquotedblleft{#1}\textquotedblright}}} \gdef\boldForm#1{\textbf{#1}} \gdef\rform#1{ {\textcolor{e1432d}{#1}}} \gdef\gform#1{ {\textcolor{4ea82a}{#1}}} \gdef\bform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \gdef\barToken{\mathbf{|}} \gdef\filledRectangleToken{▮} \gdef\emptyRectangleToken{▯} \gdef\filledToken{∙} \gdef\emptyToken{∘} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{ {#1}^{\prime}} \gdef\tinybullet{ {\tiny●}} \gdef\forwardFactor{\uparrow} \gdef\backwardFactor{\downarrow} \gdef\neutralFactor{\mid} \gdef\arrowhead{⏵} \gdef\deSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{→}}}\,}} \gdef\ueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny──}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\ldeSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{\longrightarrow}}}\,}} \gdef\lueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny────}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\de#1#2{ { {#1} \deSymbol {#2}}} \gdef\ue#1#2{ { {#1} \ueSymbol {#2}}} \gdef\tde#1#2#3{ { {#1} \overset{#3}{\deSymbol} {#2}}} \gdef\tue#1#2#3{ { {#1} \overset{#3}{\ueSymbol} {#2}}} \gdef\ltde#1#2#3{ { {#1} \overset{#3}{\ldeSymbol} {#2}}} \gdef\ltue#1#2#3{ { {#1} \overset{#3}{\lueSymbol} {#2}}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\emptySet{\empty} \gdef\unknown{\wbform{\text{?}}} \gdef\notApplicable{\wbform{\text{---}}} \gdef\isomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\defEqualSymbol{\;≝\;} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{ {\prime\prime}} \gdef\inverse#1{ { {#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{ {#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1\!\degree} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\,|\,} \gdef\groupFunction#1{#1} \gdef\gl#1#2{GL({#1},#2)} \gdef\automorphisms{\operatorname{Aut}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{ {#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\negated#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{ {\,∷\,}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\uparrow} \gdef\backwardTranslateSymbol{\downarrow} \gdef\pathTranslate#1#2{ {#1}\,\translateSymbol\,{#2}} \gdef\pathLeftTranslate#1{ {#1}{\,\translateSymbol}} \gdef\pathBackwardTranslate#1#2{ {#1}{\,\backwardTranslateSymbol\,}{#2}} \gdef\pathLeftBackwardTranslate#1{ {#1}{\,\backwardTranslateSymbol}} \gdef\forwardDifference{\Delta^{+}} \gdef\backwardDifference{\Delta^{-}} \gdef\centralDifference{\Delta} \gdef\pathForwardDifference#1{\forwardDifference_{#1}} \gdef\pathBackwardDifference#1{\backwardDifference_{#1}} \gdef\pathCentralDifference#1{\centralDifference_{#1}} \gdef\pathHeadVector#1{ {#1}^{\bullet}} \gdef\pathTailVector#1{ {#1}_{\bullet}} \gdef\pathReverse#1{ {#1}^{\dagger}} \gdef\pathIntegral#1#2{ {#1} \int {#2}} \gdef\pathIntegralSymbol{ {\int}} \gdef\pathDot#1#2{ {#1} \cdot {#2}} \gdef\pathDotSymbol{ {\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\pathWord#1#2#3{ {#1}\!:\!{#2}\!:\!{#3}} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\tvert#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\matrixDotSymbol{\cdot} \gdef\wordGroup#1{\Omega_{#1}} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{ {#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{ {#1}|{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\power#1#2{ {#1}^{#2}} \gdef\repeatedPower#1#2{ {#1}^{#2}} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{ {#1} \sim {#2}} \gdef\isContractedIn#1#2#3{ {#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{ {#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{ {#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{ {\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\covering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\powerSetSymbol{\mathsc{P}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeElement#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\symmetricGroup#1{Sym_{#1}} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\setConstructor#1#2{\left\{\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{ { {#1} \in {#2} }} \gdef\edgeOf#1#2{ { {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{ { {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{ { {#1} {\in}_P {#2} }} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\pathGroupoid#1{ { \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{ {\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{ {\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{ {\overrightharpoon{#1}}} \gdef\mto#1#2{ {#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\rewrite#1#2{ {#1}\mapsto{#2}} \gdef\rewritingRule#1#2{ {#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{ {\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathsf{#1}} \gdef\genericRewritingSystem{\namedSystem{System}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\ncard#1{\card{\negated{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\negated{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\list#1{\{ {#1} \}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{ {#1} / {#2}} \gdef\compactQuotient#1#2#3{ {#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\gmult{\,\ast\,} \gdef\Gmult{\,\ast\,} \gdef\ellipsis{\dots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\cartesianProductSymbol{\times} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\modLabeled#1#2{ {#1 }\textrm{ mod }{#2}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\,\times\,} \gdef\independentQuiverProductSymbol{\,⨝\,} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{\mid} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\!\inlineProdSymbol\!} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\indexSum#1#2#3{ {\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{ {\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{ {\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{ {\min_{#2}^{#3} #1}} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{ {#1}} \gdef\character#1{ {#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}}$$
Rewriting systems

# Rewriting systems

## Introduction

We now make our first foray into dynamics: quivers that describe systems that change in time. To do this we will use the lens of rewriting systems. A (computational) rewriting system is a non-deterministic automaton that succesively transforms some global state, represented by an arbitrary data structure, by finding and applying well-defined rules that match particular fragments of the global state, replacing them with other fragments.

Rewriting systems form a very flexible and general model of computations, and any computational system can be cast into this framework: Turing machines, cellular automata, graph rewriting systems, string rewriting systems, register machines, non-deterministic automata, etc. In all cases, these systems can be non-deterministic, although of course deterministic systems are special cases, which from our point of view will result in rather trivial theories.

Eventually, we will see how to apply discrete versions of ideas from theoretical physics to these rewriting systems, giving us computational incarnations of the ideas that underly special relativity and field theory.

## Local vs global states

The fragments we referred to earlier we'll call local states. By definition, a global state is the juxtaposition of a set of local states that together describe the state of the entire system. By a minimal local state, we mean a local state that is as granular as possible: that is not the juxtaposition of other local states. This we will refer to as a token. (There can be some freedom in how one defines the tokens in each case.)

Here we show a table indicating how this may be done for various types of system:

zzzz
system typeglobal statetoken
$$\stringRewritingSystem{}$$string rewriting systemstring $$\qstring{\character{c}_1 \character{c}_2 \ellipsis \character{c}_{\sym{n}}}$$$$\tuple{\sym{i},\character{c}_{\sym{i}}}$$
$$\turingMachineRewritingSystem{}$$Turing machinehead in state $$\sym{s}$$ at cell $$\sym{i}$$ on tape $$\qstring{\character{c}_1 \ellipsis \character{c}_{\sym{n}}}$$$$\sym{s},\sym{i},\tuple{\sym{i},\character{c}_{\sym{i}}}$$
$$\cellularAutomatonRewritingSystem{}$$cellular automatonvector of cells $$\list{\character{c}_1,\character{c}_2,\ellipsis ,\character{c}_{\sym{n}}}$$$$\tuple{\sym{i},\sym{c}_{\sym{i}}}$$
$$\graphRewritingSystem{}$$graph rewriting systemset of edges $$\list{\de{\vert{\sym{t}_1}}{\vert{\sym{h}_1}},\ellipsis ,\de{\vert{\sym{t}_{\sym{n}}}}{\vert{\sym{h}_{\sym{n}}}}}$$edge $$\de{\vert{\sym{t}_{\sym{i}}}}{\vert{\sym{h}_{\sym{i}}}}$$
$$\hypergraphRewritingSystem{}$$hypergraph rewriting systemset of hyperedges $$\list{\sym{e}_1,\sym{e}_2,\ellipsis ,\sym{e}_{\sym{n}}}$$hyperedge $$\sym{e}_{\sym{i}}$$
$$\petriNetRewritingSystem{}$$Petri netplace occupancy $$\assocArray{\mto{\sym{t}_1}{\sym{N}_1},\ellipsis ,\mto{\sym{t}_{\sym{n}}}{\sym{N}_{\sym{n}}}}$$$$\tuple{\sym{t}_{\sym{i}},\sym{N}_{\sym{i}}}$$

## Evolution

Once a particular rewriting system type has been chosen, it remains to specify the rewriting rules that should be applied. We'll indicate the system in a script typeface, typically $$\rewritingSystem{R}$$, and list its rules as:

$\rewritingSystem{R} = \rewritingRuleBinding{\genericRewritingSystem{}}{\rewritingRule{\sym{L}_1}{\sym{R}_1},\rewritingRule{\sym{L}_2}{\sym{R}_2},\ellipsis ,\rewritingRule{\sym{L}_{\sym{n}}}{\sym{R}_{\sym{n}}}}$

where $$\sym{L}_{\sym{i}}$$ is the left-hand-side, or LHS, of the $$i^{\textrm{th}}$$ rule, and $$\sym{R}_{\sym{i}}$$ is the right-hand-side, or RHS.

The LHS specifies a pattern that should match a particular local state (i.e. one or more tokens), and the RHS specifies how the matched state should be rewritten to yield a new local state (and hence a new global state). If multiple matches can occur in a given global state, the system is non-deterministic. If a maximum of one match can occur, the system is deterministic.

After specifying $$\rewritingSystem{R}$$, we can now choose an initial state, written $$\sym{s}_0$$. We write the combined data of a rewriting system and a state as $$\rewritingStateBinding{\rewritingSystem{R}}{\sym{s}_0}$$.

At that point we can evolve the system, which is an iterative process that is carried out either for a fixed number of steps, or alternatively in an ongoing fashion that never terminates. We may also reach a global state that cannot be rewritten because there are no matches: we say that a particular global state has halted.

This process generates a graph, known as a multiway graph or rewrite graph, in which vertices represent global states, and edges represent rewrites. We'll write the process that generates this graph to depth $$\sym{n}$$ as:

$\multiwayBFS{\rewritingSystem{R},\sym{s}_0,\sym{n}}$

## String rewriting systems

To illustrate this setup, we'll focus on string rewriting systems, since they are both easy to visualize, familiar to those with experience with computer programming, and fairly easy to analyze.

Our first example will be the following extremely simple system:

$\rewritingSystem{R_0}\defEqualSymbol \rewritingRuleBinding{\stringRewritingSystem{}}{\rewritingRule{\lstr{b}}{\lstr{a}}}$

This rewrite system simply replaces the letter $$\lchar{b}$$ with the letter $$\lchar{a}$$ whereever it occurs.

Here we visualize the rewrite graph generated by $$\multiwayBFS{\rewritingSystem{R_0},\qstring{\lstr{bab}}, \infty }$$:

As you can see, there are two matches for the initial state $$\qstring{\lstr{bab}}$$. In the two successor states $$\qstring{\lstr{aab}}$$ and $$\qstring{\lstr{baa}}$$ there is one match, corresponding to the remaining $$\lchar{b}$$, and in the final state $$\qstring{\lstr{aaa}}$$ there are no remaining matches as all $$\lchar{b}$$'s have been rewritten.

## Rewrite quiver

Notice the important fact here that the two matches, at positions 1 and 3 of the original string, do not overlap: we say that these rewrites commute. This implies that we can rewrite those matches in either order, and the non-rewritten match will still remain. This gives us a hint of how we might attach a cardinal structure to the rewrite graph, yielding the rewrite quiver.

Formally, the rewrite quiver is the quiver whose cardinals are the labels formed by the following data taken as a whole: the rule that was matched, and the tokens that were involved in the match.

Here we show the rewrite quiver for this simple system, where the two cardinals correspond to the two independent rewrites:

Let's consider a slightly more complex initial condition of $$\qstring{\lstr{bbb}}$$.

We can see already that this rewrite system yields a rewrite quiver given by $$\subSize{\gridQuiver{\sym{n}}}{2}$$, a hypercube of dimension $$\sym{n}$$, where $$\sym{n}$$ is the count of $$\lchar{b}$$'s in the initial condition. The rewrite quiver is insensitive to the order of the characters in the string, only depending on the $$\lchar{b}$$-count. This is a generic feature of string rewriting systems in which the rules cannot overlap.

More generally, in any global state of a rewriting system in which we have $$\sym{n}$$ commuting rewrites available, we will obtain a subquiver that is isomorphic to $$\subSize{\gridQuiver{\sym{n}}}{2}$$.

#### Sorting system

We'll now focus on the "sorting system" that partially sorts substrings:

$\rewritingSystem{R_1}\defEqualSymbol \rewritingRuleBinding{\stringRewritingSystem{}}{\rewritingRule{\lstr{ba}}{\lstr{ab}}}$

Here we show the rewrite quiver for a variety of initial conditions:

Notice the obvious fact that all of these quivers terminate in a single final state, in which the characters of the string are in sorted order. This must always happen, since a rewrite always "moves one $$\lchar{b}$$ to the right", and will always be able to do so if any $$\lchar{a}$$'s are to the right of any $$\lchar{b}$$'s. The only halting state therefore is the state in which all $$\lchar{a}$$’s are to the left of all $$\lchar{b}$$’s.

## Causality-preserving contractions

In the later sections Coverings and Contraction lattice, we introduce the notion of a quiver covering, which is a way of "gluing" or contracting vertices together in such a way that the result is still a quiver. By applying a modified form of this procedure to the rewrite quiver, we obtain "simplified descriptions" of the possible evolutions of the system, in which we conflate particular states as long as they do not violate causality. Here we show such a causality-preserving contraction lattice.

Intuitively, this object corresponds to the various ways in which we can "ignore" rewrites without violating the underlying causal order of the system. Each time we choose to "ignore" a rewrite, we will obtain a self-loop on the corresponding state.