Example rewriting systems
KnuthBendix.jl contains an internal module ExampleRWS which stores various rewriting systems used mostly for testing purposes.
ExampleRWS submodule
KnuthBendix.ExampleRWS.ZxZ — FunctionZxZ()Rewriting system of the natural presentation of
ℤ² = ⟨ a, b | a·b = b·a ⟩
ordered by LenLex order a < a⁻¹ < b < b⁻¹.
KnuthBendix.ExampleRWS.ZxZ_nonterminating — FunctionZxZ_nonterminating()Rewriting system of the natural presentation of
ℤ² = ⟨ a, b | a·b = b·a ⟩
ordered by LenLex order a < b < a⁻¹ < b⁻¹.
Knuth-Bendix completion does not terminate on this system producing an infinite set of rewriting rules of the form a·bⁿ·a⁻¹ → bⁿ.
KnuthBendix.ExampleRWS.triangle — Functiontriangle(l,n,m)Rewriting system of the monoid presentation of (l,n,m)-triangle group
⟨ a, b | 1 = aˡ = bⁿ = (a·b)ᵐ⟩
ordered by LenLex order a < b.
KnuthBendix.ExampleRWS.Sims_Example_5_4 — FunctionSims_Example_5_4()Rewriting system of the (l,n,m) = (2,3,3)-triangle group presentation
⟨ a, b, B | 1 = aˡ = bⁿ = (a·b)ᵐ = b·B = B·b ⟩
ordered by LenLex order a < b < B.
Inverse of b is specified to be B on the alphabet level.
KnuthBendix.ExampleRWS.Heisenberg — FunctionHeisenberg()Rewriting system of the group presentation of the Heisenberg group
`⟨ a, b, c | 1 = [a,c] = [b,c], [a,b] = c ⟩
ordered by WreathOrder a(6) < A(5) < b(4) < B(3) < c(2) < C(1).
Similar ordering which leads to the same confluent system is Sims_Example_5_5.
KnuthBendix.ExampleRWS.Sims_Example_5_5 — FunctionSims_Example_5_5()Rewriting system of the group presentation of the Heisenberg group
⟨ a, b, c | 1 = [a,c] = [b,c], [a,b] = c⟩
ordered by WreathOrder c(1) < C(1) < b(3) < B(3) < a(5) < A(5). Similar to Heisenberg.
This system is Example 5.5[Sims1994], p. 74.
KnuthBendix.ExampleRWS.Sims_Example_5_5_recursive — FunctionSims_Example_5_5_recursive()Rewriting system of the group presentation of the Heisenberg group
⟨ a, b, c | 1 = [a,c] = [b,c], [a,b] = c⟩
ordered by Recursive ordering c < C < b < B < a < A.
Same as Heisenberg.
KnuthBendix.ExampleRWS.triangle_237_quotient — Functiontriangle_237_quotient(n)Rewriting system of the presentation of
⟨ a, b, B | 1 = a² = b·B = B·B = b³ = (a·b)⁷ = (a·b·a·B)ⁿ ⟩
ordered by LenLex a < b < B. The presentation defines a quotient of (2,3,7)-triangle group by n-th power of the commutator [a,b].
KnuthBendix.ExampleRWS.Hurwitz4 — FunctionHurwitz4()Rewriting system of the presentation of Hurwitz group triangle_237_quotient(4).
Hurwitz4 is finite of order 168.
KnuthBendix.ExampleRWS.Hurwitz8 — FunctionHurwitz8()Rewriting system of the presentation of Hurwitz group triangle_237_quotient(8).
Hurwitz8 is finite of order 10752.
KnuthBendix.ExampleRWS.π₁Surface_recursive — Functionπ₁Surface_recursive(n)Rewriting system of the group presentation of π₁(Σₙ), the fundamental group of orientable surface of genus n:
⟨ aᵢ, Aᵢ, bᵢ, Bᵢ | 1 = Πᵢ[aᵢ, bᵢ] ⟩
ordered by Left-Recursive ordering Bₙ < bₙ < Aₙ < aₙ < ... < B₁ < b₁ < A₁ < a₁.
This terminating system was discovered by S.M.Hermiller[Hermiller1994].
KnuthBendix.ExampleRWS.π₁Surface — Functionπ₁Surface(n)Rewriting system of the group presentation of π₁(Σₙ), the fundamental group of orientable surface of genus n:
⟨ aᵢ, Aᵢ, bᵢ, Bᵢ | 1 = Πᵢ[aᵢ, bᵢ] ⟩
ordered by LenLex ordering a₁ < A₁ < a₂ < A₂ < ⋯ < aₙ < Aₙ < b₁ < B₁ < b₂ < B₂ < ⋯ < b₃ < B₃.
KnuthBendix.ExampleRWS.Coxeter_cube — FunctionCoxeter_cube()Rewriting system of the group presentation of the Coxeter group associated to cube graph.
This terminating system and its WeightedLex ordering was discovered by S.M.Hermiller[Hermiller1994].
KnuthBendix.ExampleRWS.Baumslag_Solitar — FunctionBaumslag_Solitar(m,n)Rewriting system of the group presentation of the Baumslag-Solitar group
⟨ x,y | y·xⁿ·y⁻¹ = xᵐ ⟩
ordered by WreathOrder x(1) < X(2) < y(3) < Y(4).
KnuthBendix.ExampleRWS.Fibonacci2 — FunctionFibonacci2(n)Rewriting system corresponding to monoid presentation of the Fibonacci group F(2,n)
⟨ a₁, …, aₙ | a₁·a₂ = a₃, a₂·a₃ = a₄, …, aₙ₋₁·aₙ = a₁, aₙ·a₁ = a₂⟩
ordered by LenLex ordering a₁ < a₂ < … < aₙ.
F(2,n) groups are finite for n = 2,3,4,5,7 and infinite for other ns.
KnuthBendix.ExampleRWS.Fibonacci2_recursive — FunctionFibonacci2_recursive(n)Rewriting system corresponding to monoid presentation of the Fibonacci group F(2,n)
⟨ a₁, …, aₙ | a₁·a₂ = a₃, a₂·a₃ = a₄, …, aₙ₋₁·aₙ = a₁, aₙ·a₁ = a₂⟩
ordered by Recursive ordering a₁ < a₂ < … < aₙ.
See Fibonacci2.
LenLex confluent rewriting system for $\pi_1(\Sigma_g)$
Maybe the only truly mathematically interesting rewriting system contained in ExampleRWS is the length-then-lexicographical ordering for the surface groups (i.e. the the fundamental group of orientable surface) which does not seem to be known in the mathematical literature. The author found it by accident while trying to play around and trying to force Dehn-style algorithms to produce something resembling normal forms.
Let $\pi_1(\Sigma_g) = \langle a_1,\ldots, a_g, b_1, \ldots, b_g \mid \prod_{i=1}^g a_i^{-1}b_i^{-1}a_i b_i = 1 \rangle$ be the presentation of the fundamental group of $\Sigma_g$, the orientable surface of genus $g$. Then the rewriting system consisting of the following $4g$ pairs
\[\begin{aligned} (a_1^{-1} b_1^{-1}a_1 b_1\cdots a_g^{-1}b_g^{-1}a_g b_g \quad&,\quad 1)\\ (b_1^{-1}a_1 b_1\cdots a_g^{-1}b_g^{-1}a_g b_g \quad&,\quad a_1)\\ (a_1 b_1\cdots a_g^{-1}b_g^{-1}a_g b_g \quad&,\quad b_1 a_1)\\ \vdots\\ (a_g b_g \quad&,\quad b_g a_g b_{g-1}^{-1} a_{g-1}^{-1} \cdots b_1^{-1} a_1^{-1} b_1 a_1)\\ (b_g \quad&,\quad a_g^{-1} b_g a_g b_{g-1}^{-1} a_{g-1}^{-1} \cdots b_1^{-1} a_1^{-1} b_1 a_1)\\ \end{aligned}\]
ordered by length-then-lexicographical ordering induced by
\[a_1 < a_1^{-1} < a_2 < a_2^{-1} < \cdots < a_g^{-1} < b_1 < b_1^{-1} < \cdots b_g < b_g^{-1}\]
is reduced and confluent.
- Hermiller1994Susan M. Hermiller Rewriting systems for Coxeter groups Journal of Pure and Applied Algebra, Volume 92, Issue 2, 1994, p. 137-148.
- Hermiller1994Susan M. Hermiller Rewriting systems for Coxeter groups Journal of Pure and Applied Algebra, Volume 92, Issue 2, 1994, p. 137-148.