A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods

We give basic definitions and theorems on module theory and homological algebra without proofs. For more details, readers are referred to [r10, r09] for example.

Modules are the generalization of vector spaces in which the set of scalars form a ring, not necessarily a field. {defi} Let $\mathfrak{R}$ be a ring and $(M,+)$ be an abelian group. For a map $\cdot:\mathfrak{R}\times M\rightarrow M$, $(M,+,\cdot)$ is a left $\mathfrak{R}$-module if for all $r,s\in\mathfrak{R}$ and $x,y\in M$, we have

where $rs$ denotes the multiplication of $r$ and $s$ in $\mathfrak{R}$. We call the map $\cdot$ scalar multiplication.

For a map $\cdot:M\times\mathfrak{R}\rightarrow M$, $(M,+,\cdot)$ is a right $\mathfrak{R}$-module if for any $r,s\in\mathfrak{R}$ and $x,y\in M$,

If ring $\mathfrak{R}$ is commutative, we do not distinguish between left $\mathfrak{R}$-modules and right $\mathfrak{R}$-modules and simply call them $\mathfrak{R}$-modules.

Linear maps and isomorphisms of modules are also defined in the same way as for vector spaces. {defi} For two left $\mathfrak{R}$-modules $(M_{1},+_{1},\cdot_{1}),(M_{2},+_{2},\cdot_{2})$, a group homomorphism $f:(M_{1},+_{1})\rightarrow(M_{2},+_{2})$ is an $\mathfrak{R}$-linear map if it satisfies $f(r\cdot_{1}x)=r\cdot_{2}f(x)$ for any $r\in\mathfrak{R}$ and $x\in M_{1}$. An $\mathfrak{R}$-linear map $f$ is an isomorphism if it is bijective, and two modules are called isomorphic if there exists an isomorphism between them.

Any abelian group $(M,+)$ is a $\mathbb{Z}$-module under the scalar multiplication $n\cdot x=\underbrace{x+\dotsb+x}_{n}$. {exa} For any ring $\mathfrak{R}$, the direct product $\mathfrak{R}^{n}=\underbrace{\mathfrak{R}\times\dotsb\times\mathfrak{R}}_{n}$ forms a left $\mathfrak{R}$-module under the scalar multiplication $r\cdot(r_{1},\dotsc,r_{n})=(rr_{1},\dotsc,rr_{n})$. {exa} Let $\mathfrak{R}$ be a ring and $X$ be a set. $\mathfrak{R}\underline{X}$ denotes the set of formal linear combinations

where $r_{x}=0$ except for finitely many $x$s. The underline is added to emphasize a distinction between $r\in\mathfrak{R}$ and $x\in X$. $\mathfrak{R}\underline{X}$ forms a left $\mathfrak{R}$-module under the addition and the scalar multiplication defined by

If $X$ is the empty set, $\mathfrak{R}\underline{X}$ is the left $\mathfrak{R}$-module $\{0\}$ consisting of only the identity element. We simply write $0$ for $\{0\}$. $\mathfrak{R}\underline{X}$ is called the free left $\mathfrak{R}$-module generated by $X$. If $\#X=n\in\mathbb{N}$, $\mathfrak{R}\underline{X}$ can be identified with $\mathfrak{R}^{n}$.

A left $\mathfrak{R}$-module $M$ is said to be free if $M$ is isomorphic to $\mathfrak{R}\underline{X}$ for some $X$. Free modules have some similar properties to vector spaces. If a left $\mathfrak{R}$-module $F$ is free, then there exists a basis (i.e., a subset that is linearly independent and generating) of $F$. If a free left $\mathfrak{R}$-module $F$ has a basis $(v_{1},\dotsc,v_{n})$, any $\mathfrak{R}$-linear map $f:F\rightarrow M$ is uniquely determined if the values $f(v_{1}),\dotsc,f(v_{n})$ are specified. Suppose $F_{1}$, $F_{2}$ are free left $\mathfrak{R}$-modules and $f:F_{1}\rightarrow F_{2}$ is an $\mathfrak{R}$-linear map. If $F_{1}$ has a basis $(v_{1},\dotsc,v_{n})$ and $F_{2}$ has a basis $(w_{1},\dotsc,w_{m})$, the matrix $(a_{ij})_{i=1,\dotsc,n,j=1,\dotsc,m}$ where $a_{ij}$s satisfy $f(v_{i})=a_{i1}w_{1}+\dotsb+a_{im}w_{m}$ for any $i=1,\dotsc,n$ is called a matrix representation of $f$. We define submodules and quotient modules, as in linear algebra. {defi} Let $(M,+,\cdot)$ be a left (resp. right) $\mathfrak{R}$-module. A subgroup $N$ of $(M,+)$ is a submodule if for any $x\in N$ and $r\in\mathfrak{R}$, the scalar multiplication $r\cdot x$ (resp. $x\cdot r$) is in $N$.

For any submodule $N$, the quotient group $M/N$ is also an $\mathfrak{R}$-module. $M/N$ is called the quotient module of $M$ by $N$. For submodules and quotient modules, the following basic theorem is known: {thm}[First isomorphism theorem [r10, Theorem 8.8]] Let $(M,+,\cdot),(M^{\prime},+^{\prime},\cdot^{\prime})$ be left (or right) $\mathfrak{R}$-modules, and $f:M\rightarrow M^{\prime}$ be an $\mathfrak{R}$-linear map.

1. 1.

   The inverse image of $0$ by $f$, $\ker f=\{x\in M\mid f(x)=0\}$, is a submodule of $M$.

2. 2.

   The image of $M$ by $f$, $\operatorname{im}f=\{f(x)\mid x\in M\}$, is a submodule of $M^{\prime}$.

3. 3.

   The image $\operatorname{im}f$ is isomorphic to $M/\ker f$.

[Third isomorphism theorem [r10, Theorem 7.10]] Let $M$ be a left (or right) $\mathfrak{R}$-module, $N$ be a submodule of $M$, and $L$ be a submodule of $N$. Then $(M/L)/(N/L)$ is isomorphic to $M/N$. {thmC}[[r10, Theorem 9.8]] Let $\mathfrak{R}$ be $\mathbb{Z}$ or $\mathbb{Z}/p\mathbb{Z}$ for some prime $p$. Every submodule of a free $\mathfrak{R}$-module is free. Moreover, if an $\mathfrak{R}$-module $M$ is isomorphic to $\mathfrak{R}^{n}$, then every submodule $N$ of $M$ is isomorphic to $\mathfrak{R}^{m}$ for some $m\leq n$. (In general, this holds for any principal ideal domain $\mathfrak{R}$.)

Let $M$ be a left $\mathfrak{R}$-module. For $S\subset M$, the set $\mathfrak{R}S$ of all elements in $M$ of the form $\sum_{i=1}^{k}r_{i}s_{i}$ $(k\in\mathbb{Z}_{\geq 0},r_{i}\in\mathfrak{R},s_{i}\in S)$ is a submodule of $M$. If $\mathfrak{R}S=M$, $S$ is called a generating set of $S$ and the elements of $S$ are called generators of $M$. Let $S=\{s_{i}\}_{i\in I}$ be a generating set of $M$ for some indexing set $I$. For a set $X=\{x_{i}\}_{i\in I}$, the linear map $\epsilon:\mathfrak{R}\underline{X}\ni x_{i}\mapsto s_{i}\in M$ is a surjection from the free module $\mathfrak{R}\underline{X}$. The elements of $\ker\epsilon$, that is, elements $\sum_{x_{i}\in X}r_{i}\underline{x_{i}}$ satisfying $\epsilon(\sum_{x_{i}\in X}r_{i}\underline{x_{i}})=\sum_{x_{i}\in X}r_{i}s_{i}=0$, are called relations of $M$.

Now, we introduce one of the most important notions to develop the homology theory of rewriting systems, free resolutions. We first start from the following example. {exa} Let $M$ be the $\mathbb{Z}$-module defined by

We consider the $\mathbb{Z}$-linear map between free $\mathbb{Z}$-modules $f_{0}:\mathbb{Z}^{3}\rightarrow\mathbb{Z}\underline{\{a,b,c,d,e\}}$ defined by

We can see that the image of $f_{0}$ is the set of relations of $M$. In other words, $\operatorname{im}f_{0}=\ker\epsilon$ for the linear map $\epsilon:\mathbb{Z}\underline{\{a,b,c,d,e\}}\rightarrow M$ which maps each element to its equivalence class. Then, we consider the “relations between relations”, that is, triples $(n_{1},n_{2},n_{3})$ which satisfy $f_{0}(n_{1},n_{2},n_{3})=n_{1}(\underline{a}+\underline{b}+\underline{c}-\underline{d}-\underline{e})+n_{2}(2\underline{b}-\underline{c})+n_{3}(\underline{a}+2\underline{c}-\underline{b}-\underline{d}-\underline{e})=0$, or equivalently, elements of $\ker f_{0}$. We can check $\ker f_{0}=\{m(-1,1,1)\mid m\in\mathbb{Z}\}$. This fact can be explained in terms of rewriting systems. If we write relations in the form of rewrite rules

we see $\{A_{1},A_{2},A_{3}\}$ is a complete rewriting system (over the signature $\{\underline{a},\underline{b},\underline{c},\underline{d},\underline{e},+\}$) with two joinable critical pairs

We associate these critical pairs with an equality between formal sums $A_{2}+A_{3}=A_{1}$, and it corresponds to

In fact, this correspondence between critical pairs and “relations between relations” is a key to the homology theory of TRSs.

We define a linear map $f_{1}:\mathbb{Z}\rightarrow\mathbb{Z}^{3}$ by $f_{1}(1)=(-1,1,1)$ and then $f_{1}$ satisfies $\operatorname{im}f_{1}=\ker f_{0}$. We can go further, that is, we can consider $\ker f_{1}$, but it clearly turns out that $\ker f_{1}=0$.

We encode the above information in the following diagram:

where $\operatorname{im}f_{1}=\ker f_{0},\operatorname{im}f_{0}=\ker\epsilon$ and $\epsilon$ is surjective. Sequences of modules and linear maps with these conditions are called free resolutions: {defi} A sequence of left $\mathfrak{R}$-modules and $\mathfrak{R}$-linear maps

is called an exact sequence if $\operatorname{im}f_{i}=\ker f_{i-1}$ holds for any $i$.

Let $M$ be a left $\mathfrak{R}$-module. For infinite sequence of free modules $F_{i}$ and linear maps $f_{i}:F_{i+1}\rightarrow F_{i}$, $\epsilon:F_{0}\rightarrow M$, if the sequence

is exact and $\epsilon$ is surjective, the sequence above is called a free resolution of $M$. If the sequence is finite, it is called a partial free resolution.

(Exact sequences and free resolutions are defined for right $\mathfrak{R}$-modules in the same way.) Notice that the exact sequence (3.1) can be extended to the infinite exact sequence

since $\ker f_{1}=0$. Thus, the sequence (3.1) is a free resolution of $M$.

As there are generally several rewriting systems equivalent to a given equational theory, free resolutions of $M$ are not unique. However, we can construct some information of $M$ from a (partial) free resolution which does not depend on the choice of the free resolution. The information is called homology groups. To define the homology groups, we introduce the tensor product of modules. {defi} Let $N$ be a right $\mathfrak{R}$-module and $M$ be a left $\mathfrak{R}$-module. Let $F(N\times M)$ be the free abelian group generated by $N\times M$. The tensor product of $N$ and $M$, denoted by $N\otimes_{\mathfrak{R}}M$, is the quotient group of $F(N\times M)$ by the subgroup generated by the elements of the form

where $x,x^{\prime}\in N$, $y,y^{\prime}\in M$, $r\in R$. The equivalence class of $(x,y)$ in $N\otimes_{\mathfrak{R}}M$ is written as $x\otimes y$.

For a right $\mathfrak{R}$-module $N$ and a $\mathfrak{R}$-linear map $f:M\rightarrow M^{\prime}$ between left $\mathfrak{R}$-modules $M,M^{\prime}$, we write $N\otimes f:N\otimes_{\mathfrak{R}}M\rightarrow N\otimes_{\mathfrak{R}}M^{\prime}$ for the map $(N\otimes f)(a\otimes x)=a\otimes f(x)$. $N\otimes f$ is known to be well-defined and be a group homomorphism. Let $\dotsb\xrightarrow{f_{1}}F_{1}\xrightarrow{f_{0}}F_{0}\xrightarrow{\epsilon}M$ be a free resolution of a left $\mathfrak{R}$-module $M$. For a right $\mathfrak{R}$-module $N$, we consider the sequence

Then, it can be shown that $\operatorname{im}(N\otimes f_{i})\subset\ker(N\otimes f_{i-1})$ for any $i=1,2,\dotsc$. In general, a sequence $\dotsb\xrightarrow{f_{i+1}}M_{i+1}\xrightarrow{f_{i}}M_{i}\xrightarrow{f_{i-1}}\dotsb$ of left/right $\mathfrak{R}$-modules satisfying $\operatorname{im}f_{i}\subset\ker f_{i-1}$ for any $i$ is called a chain complex. The homology groups of a chain complex are defined to be the quotient group of $\ker f_{i-1}$ by $\operatorname{im}f_{i}$: {defi} Let $(C_{\bullet},f_{\bullet})$ denote the pair $(\{C_{i}\}_{i=0,1,\dots},\{f_{i}:C_{i+1}\rightarrow C_{i}\}_{i=0,1,\dots})$. For a chain complex $\dotsb\xrightarrow{f_{i+1}}C_{i+1}\xrightarrow{f_{i}}C_{i}\xrightarrow{f_{i-1}}\dotsb$, the abelian group $H_{j}(C_{\bullet},f_{\bullet})$ defined by

is called the $j$-th homology groups of the chain complex $(C_{\bullet},f_{\bullet})$. The homology groups of the chain complex (3.2) depend only on $M$, $N$, and $\mathfrak{R}$: {thmC}[[r09, Corollary 6.21]] Let $M$ be a left $\mathfrak{R}$-module and $N$ be a right $\mathfrak{R}$-module. For any two resolutions $\dotsb\xrightarrow{f_{1}}F_{1}\xrightarrow{f_{0}}F_{0}\xrightarrow{\epsilon}M$, $\dotsb\xrightarrow{f^{\prime}_{1}}F^{\prime}_{1}\xrightarrow{f^{\prime}_{0}}F^{\prime}_{0}\xrightarrow{\epsilon}M$, we have a group isomorphism

We end this subsection by giving some basic facts on exact sequences. {propC}[[r10, Proposition 7.20 and 7.21]]

1. 1.

   $M_{1}\xrightarrow{f}M_{2}\rightarrow 0$ is exact if and only if $\ker f=0$.

2. 2.

   $0\rightarrow M_{1}\xrightarrow{f}M_{2}$ is exact if and only if $\operatorname{im}f=M_{2}$.

3. 3.

   If $M_{1}$ is a submodule of $M_{2}$, the sequence $0\rightarrow M_{2}\xrightarrow{\iota}M_{1}\xrightarrow{\pi}M_{1}/M_{2}\rightarrow 0$ is exact where $\iota$ is the inclusion map $\iota(x)=x$ and $\pi$ is the projection $\pi(x)=[x]$.

Suppose we have an exact sequence of $\mathfrak{R}$-modules $0\rightarrow M_{1}\rightarrow M_{2}\rightarrow M_{3}\rightarrow 0$. If $M_{3}$ is free, then $M_{2}$ is isomorphic to $M_{1}\times M_{3}$. The proof is given by using [r10, Proposition 7.22].

For an alphabet $\Sigma$, $\Sigma^{*}$ denotes the set of all strings of symbols over $\Sigma$. The set $\Sigma^{*}$ forms a monoid under the operation of concatenation with the empty string serving as the identity, and we call $\Sigma^{*}$ the free monoid generated by $\Sigma$. For a string rewriting system (SRS) $(\Sigma,R)$, we write $\mathcal{M}_{(\Sigma,R)}$ for the set defined by $\mathcal{M}_{(\Sigma,R)}=\Sigma^{*}\delimiter 84079374\mathopen{}\xleftrightarrow{*}_{R}$. We can see $\mathcal{M}_{(\Sigma,R)}$ is a monoid under the operations $[u]\cdot[v]=[uv]$ where $[w]$ denotes the equivalence class of $w\in\Sigma^{*}$ with respect to $\xleftrightarrow{*}_{R}$.

We say that two SRSs $(\Sigma_{1},R_{1}),(\Sigma_{2},R_{2})$ are Tietze equivalent if the monoids $\mathcal{M}_{(\Sigma_{1},R_{1})}$, $\mathcal{M}_{(\Sigma_{2},R_{2})}$ are isomorphic. It is not difficult to show that for any two SRSs $(\Sigma,R_{1}),(\Sigma,R_{2})$ with the same signature, if $R_{1}$ and $R_{2}$ are equivalent (i.e., $\xleftrightarrow{*}_{R_{1}}\,=\,\xleftrightarrow{*}_{R_{2}}$), then $(\Sigma,R_{1})$ and $(\Sigma,R_{2})$ are isomorphic. Roughly speaking, the notion that two SRSs are isomorphic means that the SRSs are equivalent but their alphabets can be different. For example, let $\Sigma_{1}$ be $\{a,b,c\}$ and $R_{1}$ be $\{abb\rightarrow ab,\ ba\rightarrow c\}$. Then, $(\Sigma_{1},R_{1})$ is isomorphic to $(\Sigma_{2},R_{2})$ where $\Sigma_{2}=\{a,b\}$ and $R_{2}=\{abb\rightarrow ab\}$. Intuitively, since $c$ is equivalent to $ba$ with respect to the congruence $\xleftrightarrow{*}_{R_{1}}$, $c$ is redundant as long as we consider strings modulo $\xleftrightarrow{*}_{R_{1}}$ and $(\Sigma_{2},R_{2})$ is the SRS made by removing $c$ from $(\Sigma_{1},R_{1})$.

If a monoid $S$ is isomorphic to $\mathcal{M}_{(\Sigma,R)}$ for an SRS $(\Sigma,R)$, we call $(\Sigma,R)$ a presentation of the monoid $S$.

Let $S$ be a monoid and consider the free $\mathbb{Z}$-module $\mathbb{Z}\underline{S}$. The module $\mathbb{Z}\underline{S}$ can be equipped with a ring structure under the multiplication $\left(\sum_{w\in S}n_{w}\underline{w}\right)\left(\sum_{w\in S}m_{w}\underline{w}\right)=\sum_{w,v\in S}n_{w}m_{v}\underline{wv}$ where $n_{w}m_{v}$ is the usual multiplication of integers and $wv$ is the multiplication of the monoid $S$. $\mathbb{Z}\underline{S}$ as a ring is called the integral monoid ring of $S$. When we think of $\mathbb{Z}\underline{S}$ as a ring, we write $\mathbb{Z}\langle S\rangle$ instead of $\mathbb{Z}\underline{S}$.

We consider $\mathbb{Z}\langle S\rangle$-modules. The group of integers $\mathbb{Z}$ forms a left (resp. right) $\mathbb{Z}\langle S\rangle$-module under the scalar multiplication $(\sum_{w\in S}n_{w}\underline{w})\cdot m=\sum_{w\in S}n_{w}m$ (resp. $m\cdot(\sum_{w\in S}n_{w}\underline{w})=\sum_{w\in S}n_{w}m\underline{w}$). Let $\dotsb\xrightarrow{\partial_{1}}F_{1}\xrightarrow{\partial_{0}}F_{0}\xrightarrow{\epsilon}\mathbb{Z}$ be a free resolution of $\mathbb{Z}$ over the ring $\mathbb{Z}\langle S\rangle$. The abelian group $H_{i}(S)$ is defined as the $i$-th homology group of the chain complex $(\mathbb{Z}\otimes_{\mathbb{Z}\langle S\rangle}F_{\bullet},\mathbb{Z}\otimes\partial_{\bullet})$, i.e.,