A string rewriting rule becomes a linear operator when words are promoted to basis vectors. Commutators of such operators generate familiar Lie algebras: sl₂, the one-sided Witt algebra, and the Heisenberg algebra. This structure lifts to Hyperstrings, directed graphs that encode sets of words. Computational experiments in Mathematica reveal the correspondence and an open puzzle about confluence diamonds.
Imagine starting with the word abba and a simple rule: whenever you see ab, swap it to ba. If we swap the first two letters of abba, we get baba. There is still an ab in the middle, so we swap it again to get bbaa. Since there are no more ab’s left, the game has to stop. This is a basic letter-swapping game, but even with just one rule, things quickly get interesting.
​
This simple game raises some fundamental questions. Does the game always stop [1]? How many moves does it take? Does the order of our moves matter, and do we get the same answers if we change the rule slightly? To approach these questions in a controlled way, we need to see what kinds of mathematical structures show up as we play.
Part I: From String Rewriting Rules to Lie Algebras

String Rewriting Rules as Linear Operators

Let’s turn our rewriting rule
R
into linear algebra. We can do this by promoting each word
S
to a state [2]. Specifically, a basis vector
|S〉
in a vector space. This lifts our rule
R
to a linear operator

R
. Now, rewriting behaves like a non-deterministic dynamical system, where the operator

R
acts as a vector field over the space of words, generating an infinitesimal transformation.​This translation makes the concept of fixed points remarkably clean. Classically, a fixed point is a “no-match” string
S
where
R(S)=S
. Linearly, this condition simply becomes

R
|S〉=0
, the operator annihilates any string with no match. To make this concrete, we construct our system on
≤n
V
, the vector space spanned by all words over an alphabet of length at most
n
.
For simplicity, we will drop the ket notation, but keep in mind we are dealing with states, not strings. The rule
wv
acts as a linear operator on the free vector space spanned by length-
n
words over the alphabet
A
, mapping each word to the formal sum of all words you get by rewriting one occurrence of
w
to
v
.
​
Because this operator eats words of length
n
and the rule changes the length by
|v|-|w|
, it spits out words of length
n+|v|-|w|
. We can think of our letters as basis vectors of
d

. Since a word is just the tensor product of its letters, the length-
n
words form a basis for
⊗n
(
d

)
. Under this view, a rewrite rule becomes a matrix.
To see this in action, look at the rules on the left. Here,
n
is the length of the input words. The rule matrix represents our rewriting rule
wv
as a linear operator on the free vector space of words over our alphabet
a
. Choosing
n
simply fixes the graded piece of the space we are acting on. On the right, you can see the resulting matrix representation, with the basis elements explicitly labeled.
Out[]=
AB, a = {A,B}, n = 2
AA
AB
BA
BB
AA
0
0
0
0
AB
1
0
0
0
BA
1
0
0
0
BB
0
1
1
0
AB, a = {A,B,C}, n = 2
AA
AB
AC
BA
BB
BC
CA
CB
CC
AA
0
0
0
0
0
0
0
0
0
AB
1
0
0
0
0
0
0
0
0
AC
0
0
0
0
0
0
0
0
0
BA
1
0
0
0
0
0
0
0
0
BB
0
1
0
1
0
0
0
0
0
BC
0
0
1
0
0
0
0
0
0
CA
0
0
0
0
0
0
0
0
0
CB
0
0
0
0
0
0
1
0
0
CC
0
0
0
0
0
0
0
0
0
AAA, a = {A,B}, n = 2
AA
AB
BA
BB
AAA
2
0
0
0
AAB
0
1
0
0
ABA
0
0
0
0
ABB
0
0
0
0
BAA
0
0
1
0
BAB
0
0
0
0
BBA
0
0
0
0
BBB
0
0
0
0
AAA, a = {A,B}, n = 3
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
AA
2
0
0
0
0
0
0
0
AB
0
1
0
0
0
0
0
0
BA
0
0
0
0
1
0
0
0
BB
0
0
0
0
0
0
0
0
On single letters, the operator
R
AB
sends
A
to
B
and annihilates
B
, meaning a word with no match maps to zero, not to itself.
​
Now, the tensor product
R
AB
⊗
R
BA
rewrites both positions of a two-letter word at the same time, sending
A⊗B
to
B⊗A
.
This is different from our full rule matrix, which sums over match positions. For example, applying
AB
to
AA
yields the superposition
AB+BA
. This sum over positions is what makes rule matrices act as derivations rather than simple substitutions, and it is the source of the non-trivial commutators we will see below.
Out[]=
A
=

1
0

B
=

0
1

AB = A⊗B
=
0
1
0
0
= e₂
R
AB
=

0
0
1
0

R
AB
.B
=

0
0
1
0


0
1

=

0
0

no match → 0
R
AB
⊗
R
BA
=
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
(
R
AB
⊗
R
BA
).(A⊗B)
=
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
=
0
0
1
0
= BA = e₃
R
AB
(n=2).AA
=
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
=
0
1
1
0
= AB + BA : sum over match positions
A rule with length change
p=|v|-|w|
is a graded operator: it maps length-
n
words to length
n+p
words. When we take the commutator of a degree-
p
and a degree-
q
operator, each factor evaluates at the correct intermediate length. This ensures both products map
⊗n
(
d

)
to
⊗(n+p+q)
(
d

)
, so they share the same, possibly rectangular, shape. The bracket is square only when
p+q=0
.​Four examples follow. First, length-preserving rules on single letters recover
[
E
12
,
E
21
]=
E
22
-
E
11
, and this same bracket at
n=2
acts diagonally with eigenvalue
#B-#A
. Second, bracketing a length-raising rule with a length-preserving one gives a rectangular, degree-1 commutator. Finally, a raising and lowering pair returns us to degree 0, with diagonal entries that count overlapping matches.
Out[]=
[E₁₂, E₂₁] = E₂₂ − E₁₁ (n=1)

0
0
1
0


0
1
0
0

−

0
1
0
0


0
0
1
0

=

-1
0
0
1

2×2, degree 0
same bracket at n=2 : #B − #A
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
−
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
=
-2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4×4, degree 0
[R(AAA), R(AB)] : degree +1, rectangular
1
0
0
0
0
0
0
0

0
0
1
0

−
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
=
0
0
-1
0
-1
0
0
0
4×2, degree 1
[R(AAA), R(AAA)] : raising/lowering, diagonal
1
0
0
0
0
0
0
0

1
0
0
0
0
0
0
0

−
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
=
-3
0
0
0
0
-1
0
0
0
0
-1
0
0
0
0
0
4×4, degree 0

The Lie Algebra Search

Our search separates into two distinct regimes. Brackets of rules like
a
m
a
and
a
n
a
keep producing longer and longer words, so the operators never stop generating new ones: the algebra is infinite-dimensional. Finite-dimensional algebras appear only when the growth is cut off, words beyond a fixed length are quotiented to zero.
​
One infinite family can be handled exactly: the rules
a
k+1
a
generate the one-sided Witt algebra, proven by hand (proof not shown here); the section below exhibits the structure computationally.

Roots and the Weight Lattice

We can project words in the alphabet
{A,B}
to the lattice
2

by counting their letters [3]: each word maps to its weight
(#A,#B)
. The first picture shows the weight of the word
ABAB
at the point
(2,2)
, while the board lists the full weight space at
(2,2),
all six words with two
A
’s and two
B
’s.
​
A rewrite rule
ABB
shifts every word’s letter count by the same fixed vector,
(-1,0)
. This vector acts as a root: on the lattice, the rule simply translates weights, shown by the arrow from
(2,2)
to
(1,2)
. The last panel shows the rule acting directly on words. Because
ABAB
contains the pattern
AB
at two positions, the rule maps it to two words,
BAB
and
ABB
, both of weight
(1,2)
. Here in the lattice, the rule is a simple translation.
Out[]=
Weight space at {2, 2}
AABB
ABAB
ABBA
BAAB
BABA
BBAA
With this setup, we can ask some fascinating questions. Can we find rules that satisfy

R
i
,
R
j
=γ
R
k
? Our target is a set of at least three rules where every pairwise bracket yields a scalar multiple of a single rule in the set, with no general linear combinations allowed. This condition is much stricter than the usual closure studied in rule algebras. For instance, a set like
{
E
ab
,
E
ba
,
E
bb
-
E
aa
}
closes as a linear span, but it fails our test because
E
bb
-
E
aa
is not a single rule.​To find these sets, we filter before we search. Each rule can be a vector, which is the net change in letter counts
(Δ#A,Δ#B,Δ#C)∈
|alphabet|

. Because the bracket is additive on weights, the relation

R
i
,
R
j
=γ
R
k
forces the weights to add up, meaning
wt(
R
k
)=wt(
R
i
)+wt
R
j

. This simple arithmetic condition filters away most candidate triples before we compute a single commutator, leaving only a few surviving clusters to test exhaustively.​We run our search over all rules
uv
over alphabets of size 1, 2, and 3, restricting the input length
|u|∈{1,2,3}
and the output length
|v|∈{0,1,2,3}
. We partition the search space by alphabet size.

Alphabet {A}

The two search cells below were generated with AI assistance (Claude Fable 5) . The reported witnesses were confirmed by independent runs, but the author has not audited the search code line by line . Readers are welcome to run, modify, and stress - test it .

Alphabet {A, B}

We establish an explicit certificate: any candidate rule must have a footprint of at most 6, which bounds the search.

Alphabet {A, B, C}

Everything so far acts on one string at a time. A rule takes a word, finds a match, and produces another word, with the operators of Part I organized sector by sector and length by length. But the objects of real interest are often sets of words, such as the reachable states of a rewriting system, the value sets of a computation, or a formal language. This raises a natural question: is there a single finite object that carries a whole family of strings at once, on which rewriting can act directly?
​
There is: a hyperstring, which is a directed acyclic graph whose paths spell words. The rest of this essay develops hyperstrings, shows that rewriting them matches rewriting every individual string they carry, and verifies that the Lie algebra structure of Part I survives this lift intact.
Part II: Hyperstring

Definition of a Hyperstring

Mapping Between Strings and Hyperstrings

Claim:
​HyperstringToStrings ∘ StringsToHyperstring is the identity on nonempty finite string sets.
Hence StringsToHyperstring is injective, HyperstringToStrings is surjective, and each string set L is recovered exactly from the hyperstring built from it:

Witnesses of the claim:

For all nonempty finite L, HyperstringToStrings(StringsToHyperstring(L)) = L:
StringsToHyperstring(L₁) = StringsToHyperstring(L₃) ⟹ L₁ = L₃:
For every L there exists H with HyperstringToStrings(H) = L:

Hyperstring Rewriting Rules

Rules as graph pairs

Matching and applying a rule

Two Ways to Rewrite: Fresh or Shared Vertices

Sliced Rewriting

Pushforward: The Lie Algebra Structure Lifts to Hyperstrings

The Commuting Square

Route 1: Hyperstring, Rewrite, Then Read Off Words

H:
moving along the upper arrow to R(H):
moving down to HyperstringToString(R(H)):

Route 2: Hyperstring, Read Off Words, Then Rewrite

moving down from H to HyperstringToString(H):

Lie Structure on Hyperstrings

Recall

One-Sided Witt

Heisenberg

Final thoughts: Diamonds, An Open Puzzle

Now let' s look at a random Hyperstring over the alphabet {X, Y, Z}:
• Why does the shared mode have fewer diamonds overall? ​
• How do asymmetric diamonds form only in fresh mode? ​
• How can we have an arm of length 4 at depth 3?
• ...
While commutators show us which rules generate which Lie algebras, and the pushforward proves this structure survives the transition from strings to Hyperstrings, the diamonds are counting something else: not what the operators are, but how their applications interleave and collide [1] [7].
​
Whether that geometry can be organized by an algebraic invariant of its own, or whether it reflects a purely combinatorial behavior that no bracket can capture, remains open. All of the code in this notebook is self-contained; any reader with a spare afternoon and a fresh kernel is warmly invited to find out.

Acknowledgements

The author thanks Stephen Wolfram for proposing the term Hyperstring, and Pavel Hajek for his guidance, mathematical inspiration, and helpful discussions.

References

[1] M. H. A. Newman (1942), “On Theories with a Combinatorial Definition of ‘Equivalence’,” Annals of Mathematics 43(2), 223–243.
[2] N . Behr, V . Danos and I . Garnier (2016), "Stochastic Mechanics of Graph Rewriting," Proceedings of the 31 st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS' 16), 46–55. https : // doi . org/10.1145/2933575.2934537
[3] W. Fulton and J. Harris (1991), Representation Theory: A First Course, Graduate Texts in Mathematics 129. Springer-Verlag.
[4] P. Hajek (2025), “Lie Brackets on Hypergraphs,” Wolfram Community. https://community.wolfram.com/groups/-/m/t/3358052
[5] S. Wolfram (2020), “A Class of Models with the Potential to Represent Fundamental Physics,” Complex Systems 29(2), 107–536. https://doi.org/10.25088/ComplexSystems.29.2.107
[6] P. Blasiak, G. H. E. Duchamp, A. I. Solomon, A. Horzela and K. A. Penson (2010), “Combinatorial Algebra for Second-Quantized Quantum Theory,” Advances in Theoretical and Mathematical Physics 14(4), 1209–1243. https://arxiv.org/abs/1001.4964
[7] G. M. Bergman (1978), “The Diamond Lemma for Ring Theory,” Advances in Mathematics 29(2), 178–218.

AI Disclosure

The following generative AI tools were used in this project: Claude Fable 5 (Anthropic). It was used for brainstorming, reference search, debugging code, and editing prose. All written content and code was reviewed, tested, and approved by the author, with one exception: the two exhaustive search cells in Part I (alphabet sizes 2 and 3) were reviewed and their outputs spot checked, but are provided primarily as exploratory code for readers to run and modify rather than as verified results.

CITE THIS NOTEBOOK

Lie Algebras from Strings to Hyperstrings​
by Sally Li​
Wolfram Community, STAFF PICKS, July 16, 2026
​https://community.wolfram.com/groups/-/m/t/3762249