The system S terminates because the rules are length preserving, and every rewriting step reduces words lexicographically. A direct consideration of the critical pairs provides local confluence. For instance, we have and for a, b, c ∈ Σ, a < b < c, (c, bu) ∈ I, (a, bcuυ) ∈ I.

In particular, we can decide the word problem for M (Σ, I) by determining irreducible normal forms. The set IRR(S) describes the set of the lexicographic normal forms. Since all defining relations are length preserving any lexicographic normal form is in length-lexicographic normal form, too.

Analogously to the monoid case, free partially commutative groups are defined as follows:

Free partially commutative groups have long been studied in mathematics and play a prominent role. Various names have been introduced for them. They are also called graph groups because the defining relations are given by an undirected graph, or right-angled Artin groups (or RAAGs for short). This naming is explained by the fact that, in the plane, reflections at orthogonal straight lines commute. Graph groups can be embedded into right-angled Coxeter groups. The names refer to Emil Artin (1898–1962) and Harold Coxeter (1907–2003). Coxeter groups also have a direct geometric interpretation and several textbooks are devoted to their rich and beautiful theory [7, 20].

Free partially commutative monoids can be embedded into free partially commutative groups, exactly as free monoids are submonoids of free groups. To see this, consider where is a disjoint copy of Σ. We extend the map a ↦ a̅ to an involution on Γ by for all a ∈ Γ. Then we extend the relation I to Γ by adding the pairs (a, b̄), (a̅, b), (a̅, b) for (a, b) ∈ I. Moreover, we order Σ linearly by ≤ and extend this linear order to Γ in a special unique way. We require that for all a, b ∈ Σ with a < b, we have a < a̅ < b in Γ. With this trick, the following semi-Thue system is convergent:

We obtain G(Σ, I) = Γ∗/SG. Note that the system S in (8.3) is a subset of SG such that IRR(S) ⊆ IRR(SG). This is enough to imply an inclusion of monoids

As M (Σ, I) is a submonoid of some group, it is cancellative. This means pυq = pwq implies υ = w for all elements p, q, υ, w. With the help of SG, we may solve the word problem for the group G(Σ, I). Due to the rules aa → 1 the set IRR(SG) consists of the length-lexicographic normal forms. In a suitable implementation, computing irreducible normal forms can be done in linear time [112].

There is another way to see that free partially commutative monoids embed into groups by embedding M(Σ, I) first into a direct product of free monoids. This is enough because a direct product of free monoids canonically embeds in a direct product of free groups. Since the embedding into a direct product of free monoids is a key property in the theory of free partially commutative monoids, we work this out in detail; and we actually prove a more general result.

The specification of M (Σ, I) has been given by an undirected graph (Σ, I) without loops and multiple edges; but we may also consider its complement graph (Σ, D). Thus, a, b ∈ Σ are connected by an edge in (Σ, D) if a ≠ b and (a, b) ∉ I. We call (Σ, D) a dependence alphabet. A morphism f : (Σ, D) → (Σ' , D) is given by a mapping f : Σ → Σ' which maps edges (a, b) ∈ D to edges (f(a), f(b)) ∈ D. We say that f is an epimorphism if it is surjective on vertices and edges. Given a morphism f : (Σ, D) → (Σ' , D), we can define a homomorphism f ∗ : M(Σ' , I) → M(Σ, I) in the other direction by

Note that f ∗(a) is well defined since (Σ' , D) has no self-loops and edges must be mapped to edges. (In a slightly more general setting, we could allow self-loops and then we just decide on some ordering in the product to define f ∗(a).) The important point is that f ∗ is well defined as a homomorphism. Indeed, let (a' , b) ∈ I, then we have a' ≠ b' and there is no edge between a' and b' in the graph (Σ' , D) (whether or not there are self-loops). Hence, there cannot be any edge between the sets f −1(a) and f −1(b) in (Σ, D). This means (a' , b) ∈ I' implies f ∗(a)f ∗(b) = f ∗(b)f ∗(a). Hence, f ∗ : M(Σ' , I) → M(Σ, I) is well defined.

Proposition 8.15. Let f : (Σ, D) → (Σ' , D) be a morphism between dependence alphabets. Then f is an epimorphism if and only if f ∗ : M(Σ' , I') → M(Σ, I) is injective.

Proof: If f is not an epimorphism, then either a vertex a' or an edge (a' , b') ∈ D' is not in the range of f . In the former case we have f ∗(a') = 1 and in the latter case we have f ∗(a'b') = f ∗(b'a') but a'b' ≠ ba' in M(Σ' , I). For the other direction, it is enough to recover w' ∈ M(Σ' , I') from its image f ∗(w') ∈ M(Σ, I). This is clear for |w'| ≤ 1. Hence we may assume that |w'| > 1. To handle this case endow Σ' and Σ with linear orderings such that a' < b' in Σ' implies a < b in Σ for all a ∈ f −1(a') and b ∈ f −1(b'). Next, compute the lexicographical normal form ŵ for f ∗(w'). In order to check that a' ∈ Σ' is the first letter in the lexicographical normal form for w', we consider all b' ∈ Σ' with a' ≠ b'. If (a' , b) ∈ D', then there are (a, b) ∈ D with f(a) = a' and f(b) = b', because f is surjective on edges. In this case, the first a must be before all b in ŵ. If (a' , b') ∈ I', then f −1(a') and f −1(b') are not empty because f is surjective on vertices. In this case all letters of f −1(a') appear in ŵ before any letter of f −1(b') appears in ŵ. This is due to the choice of the linear order on Σ. Once a' is detected, we are done by induction since M (Σ, I) is cancellative: either by the inclusion (8.5) or by a simple direct argument using the defining relations ab = ba for (a, b) ∈ I.

□

Corollary 8.16. Let M (Σ, I) be a trace monoid andD the collection of subsets {a, b} ⊆ Σ such that (a, b) ∉ I (including the case a = b). For each {a, b} ∈ ? let πab be the natural projection of M (Σ, I) onto the free monoid {a, b}∗, which is defined by erasing all letters different from a, b. Then, we obtain a canonical embedding

In particular, every trace monoid is a submonoid of a finite direct product of finitely generated free monoids; and therefore its word problem is solvable in linear time.

The analog of Proposition 8.15 and Corollary 8.16 fails for free partially commutative groups. For example, consider Σ = {a, b, c} with the linear order a < b < c, where a and c are independent, but (a, b) ∉ I and (b, c) ∉ I. For group elements x, y, let [x, y] = xyx−1y−1 denote the commutator of x and y. It turns out that the lexicographical normal form of [[a, b], [c, b]] is the word

In particular, [[a, b], [c, b]] ≠ 1 in G(Σ, I). There are two projections πab and πbc of G(Σ, I) onto F(a, b) and F(b, c), respectively. However, πab([c, b]) = 1 and πbc([a, b]) = 1. Hence, π[[a, b], [c, b]] = 1 in the direct product F(a, b) × F(b, c). Actually, the graph group F(a, b, c)/{ac = ca} is no subgroup of any finite direct product of free groups [35]. The subgroup structure of RAAGs is rich and complicated. It has been studied from various angles which go far beyond the scope of this textbook. For more advanced topics, see, for example [34, 111].

Based on (Σ, I) the right-angled Coxeter group C (Σ, I) is defined as follows:

These Coxeter groups are therefore quotients of the respective graph groups. Since nontrivial Coxeter groups have torsion, they cannot appear as subgroups of graph groups.However, every graph group is a subgroup of some right-angled Coxeter group, see Exercise 8.4.

8.7 Semidirect products

The construction of semidirect products follows the scheme we have seen in the construction of free products in Example 8.7. We let M and K be monoids with associated (potentially infinite) alphabets ΣM = M {1} and ΣK = K {1}. We assume that these alphabets are disjoint, and the monoids share the neutral element 1. The notion of semidirect product refers to M, K and a monoid homomorphism α : K → Aut(M), where Aut(M) is the automorphism group of the monoid M. For instance, K = M = ℤ (with common neutral element 0) and α(x)(m) = (−1)x ⋅ m. In this section, we write x m instead of α(x)(m) for x ∈ K and m ∈ M. In this notation, we obtain

The idea now is to realize x m as an inner automorphism xmx−1 = xm. For monoids there is no x−1, in general. Hence, we replace the equation xmx−1 = x m by xm = x mx, which is equivalent in the group case and makes sense in all monoids. As for free products, let Σ = ΣM ∪ ΣK and S = SM ∪ SK. We extend S to a system Sα by

The system Sα terminates because it reduces length-lexicographically if we choose the letters from ΣM smaller than those from ΣK. Local confluence follows from the above computation rules. Hence, the system Sα is convergent. The normal form computation pushes the elements of K to the right. Then we may interpret IRR(Sα) as the set of pairs in M × K.

The semidirect product M ⋊α K is defined by the set M × K together with the multiplication

By construction M ⋊α K = Σ∗/Sα is the quotient monoid of the free product M ∗ K with the (additional) defining relations xm = x mx.

Moreover, M and K are embedded in M ⋊α K via M ≅ M ×{1} and K ≅ {1}×K which means that we may consider M and K as submonoids of M ⋊α K. If M and K are groups, then M is a normal subgroup; the conjugation action (1, x)(m, 1)(1, x−1) with x ∈ K, m ∈ M, results in (xm, 1) = (α(x)(m), 1) and, therefore, it becomes an automorphism α(x) ∈ Aut(M).

As an example, we now consider the case K = M = ℤ. There are exactly two semidirect products, the direct product and the non-Abelian group ℤ ⋊ ℤ with the multiplication

For the case K = ℤ/2ℤ and M = ℤ, the situation is quite similar. We also get only one non-Abelian semidirect product ℤ ⋊ (ℤ/2ℤ) with the multiplication as above, but in the second component the computation is modulo 2.

Example 8.17. The following are typical instances of semidirect products:

The proof that BS(1, 2) and are isomorphic is along the same lines as above. For BS(1, 2), we map a to (1, 0) and t to (0, 1) in The defining relation tat−1 = a2 holds in the elements (1, 0) and (0, 1) generate the semidirect product; and, finally, the normal form description in Equation (8.1) shows that a ↦ (1, 0), t ↦ (0, 1) induces an injection.

◊

8.8 Amalgamated products and HNN extensions

We explain the construction of amalgamated products and HNN extensions for groups, only. We start with the amalgamated product and consider three groups U, G, and H together with two injective homomorphisms φ: U → G and ψ: U → H. For example, U, G and H just can be the finite cyclic groups ℤ/2ℤ, Z /4ℤ and Z /6ℤ, respectively.

We now define the amalgamated product G ∗U H as the quotient group of the free product G ∗ H by

We recognize the following universal property: the homomorphisms from G ∗U H to a group (or a monoid) K correspond exactly to the pairs (g, h) of homomorphisms g : G → K and h : H → K which fulfill the condition

g(φ(u)) = h(ψ(u)) for all u ∈ U

In Section 8.12,we consider the special linear group SL(2, ℤ) of 2 ×2 matriceswith coefficients in ℤ and determinant 1. If we choose and then S hasorder 4 and R has order 6. In fact, we have and In particular, we obtain a pair of homomorphisms ℤ/4ℤ→ SL(2, ℤ) with 1 mod 4 ↦ S and ℤ/6ℤ → SL(2, ℤ) with 1 mod 6 ↦ R. Due to the universal property of amalgamated products, there is a homomorphism of (ℤ/4ℤ) ∗ℤ/2ℤ (ℤ/6ℤ) in SL(2, ℤ) because of the relation S2 = R3. Theorem 8.38 shows that this homomorphism in fact is an isomorphism.

Let us return to the general situation G ∗ H/{ φ(u) = ψ(u) | u ∈ U }. It is a priori unclear whether the natural maps G → G ∗U H and H → G ∗U H are injective. In principle, G ∗U H could be the trivial group. However, this is not the case; and to prove thiswe introduce a convergent semi-Thue system S ⊆ Σ∗ ×Σ∗ which represents G ∗U H. Here S and Σ will be infinite if G ∪ H is infinite.

For this, we just may consider the situation that φ: U → G and ψ: U → H are inclusions and that G ∩ H = U. This simplifies the notation.

We now divide G and H into cosets of U. For this, we choose a complete system A ⊆ G of (left) coset representatives of U in G with 1 ∈ A and a complete system B ⊆ H of (left) coset representatives of U in H with 1 ∈ B. As alphabets we choose ΣA = (U ∪ A) {1} and ΣB = (U ∪ B) {1} and Σ = ΣA ∪ ΣB. Each element g ∈ G ∪ H has a unique representation as a word cu ∈ Σ∗ with c ∈ A ∪ B and u ∈ U. (For the neutral element 1 ∈ G ∪ H, we have c = u = 1 ∈ A ∩ B ∩ U, and cu = 1 is the empty word.) More precisely, there is a representation of length 0 (g = 1), length 1 (1 ≠ g ∈ U ∪ A ∪ B) or length 2 (otherwise).

Theorem 8.18. The semi-Thue system S of (8.7) is convergent and Σ∗/S is canonically isomorphic to the amalgamated free product G ∗U H.

Proof: First, we convince ourselves that Σ∗/S and G ∗U H are isomorphic. The isomorphism is induced by the natural inclusions ΣA → G and ΣB → H. It is therefore canonical, and this justifies the notation Σ∗/S = G ∗U H. Because ΣA ∩ ΣB ⊆ U, the natural homomorphism Σ∗ → G ∗U H is well defined since in the amalgamated product all u ∈ G ∩ U are identified with u ∈ H ∩ U. The group G ∗U H is generated by the elements of G and H, and these generators can already be represented by words from Σ∗ with length at most two. So the map Σ∗ → G ∗U H is surjective. Due to the claims [υw] = [au] and [υw] = [bu], also the induced map π : Σ∗/S → G ∗U H is well defined and a surjective homomorphism.We have to show that π is injective.

□

For this purpose, we define the maps φG : G → Σ∗/S and φH : H → Σ∗/S by φG(g) = au and φH(h) = bu if [g] = [au], a ∈ A, u ∈ U and [h] = [bu], b ∈ B, u ∈ U, respectively. These maps are well defined, because A and B are complete sets of representatives of the left cosets of U in G and H, respectively. We have to show that φG and φH are homomorphisms. Here the system S comes into play. Let φG(g) = au, φG(g) = au' and φG(gg') = au. With a maximum of four rewriting steps, we obtain

It follows that φG is a homomorphism. Analogously, φH is a homomorphism. For all u ∈ U = G ∩ H we have φG(u) = φH(u) which means that φG and φH induce a homomorphism φ: G ∗U H → Σ∗/S. Finally, φ(π(c)) = c for all c ∈ Σ which gives that π is injective. The proof that Σ∗/S = G ∗U H was a bit tedious, but purely mechanical. Next, we show that the system S is convergent. This requires to prove termination and local confluence. We start with the termination.

Let x ∈ Σ∗ be a word of length n. We show that for x at most (n2) rewriting steps are possible. There are at most n length reductions. Let now C = Σ U. We consider the length-preserving rule υw → cu with c ∈ A ∪ B, u ∈ U. Then |cu| = 2 and c ∈ C. For w ∈ U, we would get υ = c which is excluded. Hence, without loss of generality, let w = a' ∈ A, and then also c = a ∈ A. For υ ∈ A the rule has the form aa' → au. An application of the rule aa' → au reduces the number of letters from C. Therefore, altogether a rule of this type can be applied at most n times because no rule application increases the number of letters from C. Thus it is enough to count how often a rule of the type ua' → au with a, a' ∈ A and u, u' can be applied. By such a rule application a letter from U moves to the right, and this can happen at most n times per letter before it reaches the right end. Since we have at most n letters from U, we therefore obtain a maximum of (n2) rule applications.

The proof of the local confluence is pure routine by considering all critical pairs. The critical pairs arise from words of length 3. In such a word, all three letters either belong to ΣA or belong to ΣB. Indeed, if a word υuw consisting of three letters υ, u, w has the middle letter u ∈ U, then either υu is irreducible or υ ∈ U. All words whose letters belong entirely to ΣA or to ΣB have an interpretation in G or H and therefore a unique irreducible normal form, either the form au or the form bu with a ∈ A, b ∈ B and u ∈ U. Thus, the system S represents the amalgamated product G ∗U H and is convergent.

A direct consequence of Theorem 8.18 is that G and H embed themselves in G ∗U H as desired: all words of the form au or bu with a ∈ A, b ∈ B and u ∈ U are irreducible. This implies the announced embedding of G∪H into the amalgamated product G ∗U H.

The normal forms in IRR(S) consist of alternating sequences of letters from A and B, and, possibly, a last letter from U. Therefore, each word w ∈ IRR(S) can be written as

with m ≥ 0, and all ai ∈ A, bj ∈ B and u ∈ U. If we require that, in addition, ai ≠ 1 for 2 ≤ i ≤ m and bj ≠ 1 for 1 ≤ j < m, then the representation is unique.

For many applications, this system S is unnecessarily meticulous. Often we content ourselves with the alphabet Γ = (G ∪ H) {1} and rules which reduce words of length 2 or 3 to words in Γ ∪ {1} in each step.

For this purpose, define S' as follows:

If we start with a word w ∈ Γ∗, then we obtain an irreducible sequence relating to S' of the form

with n ≥ 0, where for n ≥ 1, we have gn , gi ∈ Γ, and gi ∈ G ⇔ gi+1 ∉ G for all 1 ≤ i < n. To implement this effectively, we assume that G is finitely generated by an alphabet Γ0 and H is finitely generated by an alphabet Γ1 where Γ0 ∩ Γ1 = 0. We further assume that we can effectively determine if a word belongs to U. Also we assume that, for a word we can effectively compute a representation as a word in Finally, we must be able to decide whether g = 1 for

Let us summarize this again. The word problem in G ∗U H is solvable if the following conditions are satisfied: the word problems in G and H are solvable, the membership problem for the subgroup U is solvable in G and H, and for u ∈ U, we can effectively switch between the representations as words in Γ∗0 and Γ∗1 .

We now consider another important construction in combinatorial group theory, the HNN extensions which are named after their inventors Graham Higman (1917–2008), Bernhard Hermann Neumann (1909–2002), and Hanna Neumann (1914–1971). Their explicit construction is given in [50].

We start with a group G and an isomorphism φ: A → B between subgroups A and B of G. The central idea is to embed G into a bigger group in which φ becomes an inner automorphism, that is, φ is realized by an element t with tat−1 = φ(a) for all a ∈ A. The required property leads to the following construction. Let t be a new symbol and F (t) the free group generated by t; then, we have F (t) ≅ ℤ. The HNN extension of G with respect to φ: A → B is the following quotient group:

In order to see that G and F (t) can be embedded into the HNN extension, we argue analogously as in the case of amalgamated products. The formal proofs just follow the already known technique step by step.

As the alphabet we now choose Σ = {t, t} ∪ (G {1}), and thus obtain a canonical surjective homomorphism Σ∗ → HNN(G; A, B, φ). We choose a complete system C ⊆ G and D ⊆ G of (left) coset representatives of A in G with 1 ∈ C and of B in G with 1 ∈ D, respectively. Each g ∈ G has a unique representation g = ca = db with a ∈ A, b ∈ B, c ∈ C, and d ∈ D. In the HNN extension we have: gt̄ = cat̄ = ct̄φ(a) and gt = dbt = dtφ−1(b). Therefore, we may push the elements of A to the right by means of t−1 = t̄ and analogously the elements of B by means of t. The representatives remain on the left side. This consideration leads us to the following semi-Thue system S:

The isomorphism between Σ∗/S and HNN(G; A, B, φ) and the local confluence of S are easy to prove, that is, they are purely mechanical and analogously follow the scheme we had for amalgamated products. Some more attention we have to pay to the termination since the system S even increases lengths. Again, let x ∈ Σ∗ be a word of length n. First, we mark all letters in the word except the t’s and the t’s. Then we remove the marking for those 1 ≠ c ∈ C and 1 ≠ d ∈ D where there is a t or t, respectively, on the right. This rule for the markings we retain during the rewriting steps. After a rule application, a new marking can only be generated if, for instance, there is a factor ctt and tt gets deleted. This reduces the number of t’s, and the number of marks is therefore limited in total by n. Hence, each rule application reduces the number of t’s or it reduces the number of markings or some marking will be passed exactly one position closer to the right edge. We thus obtain a maximum of n2 possible rewriting steps.

In particular, we obtain the following theorem:

Theorem 8.19. The system S of equation (8.8) is convergent, and Σ∗/S is canonically isomorphic to the HNN extension

From Theorem 8.19, we obtain that the irreducible normal forms for HNN extensions have the following unique representation:

with n ≥ 0, h ∈ G and either ri ∈ C and θi = t or ri ∈ D and θi = t for all 1 ≤ i ≤ n. In particular, G and F (t) embed into the HNN extension, and the HNN extension is always a group that has ℤas a quotient group and, therefore, contains ℤas a subgroup, too. As in the case of amalgamated products the system S from (8.8) is unnecessarily meticulous. In order to solve the word problem, we do not need a unique normal form. It is enough to consider Britton reductionswhichwere introduced in [10] by JohnLeslie Britton (1927–1994). By definition, a Britton reduction means to apply one of the following rules:

The new system is length reducing and for each word from Σ∗ it provides a Britton reduced word of the form

with n ≥ 0, g1, . . . , gn, h ∈ G, and θi ∈ {t, t̄} for i = 1, . . . , n and gi ≠ 1 for 2 ≤ i ≤ n. This Britton reduced normal form is not unique: for instance, tφ(b) and bt are both Britton reduced but represent the same element in HNN(G; A, B, φ). Let g = g1θ1 ⋅⋅ ⋅ gnθnh be Britton reduced and θ1, . . . , θn the sequence of the occurring t’s and t̄’s. If we now further apply rules from the convergent system S of (8.8), then we realize that the sequence θ1, . . . , θn does not change anymore. This sequence is therefore determined solely by the group element g. Hence, g ∈ G if and only if n = 0 and h = 1. If G has a solvable word problem and if we can effectively compute Britton reductions, then the HNN extension G ∗ F (t)/{ tat−1 = φ(a) | a ∈ A } has a solvable word problem.

Example 8.20. The Baumslag–Solitar groups BS(p, q) defined in Example 8.8 are HNN extensions of ℤ. The Waack group W defined in Example 8.9 is an HNN extension of BS(1, 2) = F (a, t)/{tat−1 = a2}. Actually, we presented two different realizations: BS(1, 2) ∗ F(s)/{sas−1 = a2} and BS(1, 2) ∗ F(r)/{rar−1 = a}. Thus, different looking HNN extensions may define isomorphic groups.

◊

The similarity of the constructions for amalgamated products and HNN extensions is not a coincidence: it is part of the Bass–Serre theory. This theory was outlined by Jean-Pierre Serre (born 1926) [93] and brought to its final form by Hyman Bass (born 1932).

The Baumslag group BG(1, 2)

Let us consider another HNN extension BG(1, 2) given as

It is called the Baumslag group. The generator t is redundant and BG(1, 2) is generated by a and b with a single defining relation

At first glance, this might appear to be a similar definition as the one for the Waack group W above. However, the behavior is quite different. Baumslag constructed his group BG(1, 2) as an example of a not cyclic one-relator group where all its finite quotients are cyclic. Later Gersten showed that the so-called Dehn function grows faster than any elementary function. We do not define these notions here, but due to the discovery of Gersten, the group BG(1, 2) is called the Baumslag–Gersten group in the literature [84], too.

The word problem in BG(1, 2) is solvable because we can effectively compute the Britton reduced normal form as follows. The input is a word w ∈ {a, a−1, b, b−1, t, t−1}∗, which we decompose

with m ≥ 0, βi ∈ {b, b−1}∗ and gi ∈ {a, a−1, t, t−1}∗.

If m = 0, then w = g0 ∈ BS(1, 2) is Britton reduced. If m = 1, then w ∉ BS(1, 2), and w is Britton reduced. Now, let m ≥ 2. We consider all factors of the form βigiβi+1 with 1 ≤ i < m. If βi = b, then we test if has the form gi = (τ, 0) with τ ∈ ℤ. If yes, then gi = aτ in BS(1, 2), and we replace the factor βigiβi+1 by tτ or (0, τ), respectively, if we calculate directly in the decomposition Analogously, if βi = b−1 and gi = (0, τ) with τ ∈ ℤ, then we replace βigiβi+1 by aτ or (τ, 0), respectively. After a maximum of m such steps, we obtain a Britton reduced word.

This looks harmless enough, but lo and behold, the exponents can get huge very quickly; see Exercise 8.11. This is closely related to the fast growing Dehn functions; and for this reason, the group BG(1, 2) for many years was a candidate for a one-relator group with an extremely difficult word problem. However, it had to be canceled from that list by [31, 78]: the word problem for BG(1, 2) is solvable in cubic time using a data structure called power circuit.

8.9 Rational sets and Benois’ theorem

As usual if M is a monoid and R, R' subsets of M, then R ⋅ R' denotes the product R ⋅ R' = {xy ∈ M| x ∈ R, y ∈ R' } and R∗ denotes the submonoid of M, which is generated by R. Ifwe let R0 = {1} and Rn+1 = R ⋅ Rn, we have R∗ = ⋃{ Rn | n ∈ ℕ}. As in Section 7.2, we define the family RAT(M) of rational sets inductively: