Printer Friendly

A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups.

Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it. Keywords: epigroup, finite semigroup, decidability of equational theory, finite basis problem

1 Introduction

A semigroup S is called an epigroup if, for every element x [member of] S, some power of x belongs to a subgroup of S. The class of all epigroups includes all periodic semigroups (i.e., semigroups in which each element has an idempotent power), all completely regular semigroups (i.e., unions of groups), and many other important classes of semigroups. See Shevrin (1994a,b) and the survey Shevrin (2005) for more examples and an introduction to the structure theory of epigroups.

It is known that, for every element x of an epigroup S, there exists a unique maximal subgroup [G.sub.x] that contains all but finitely many powers of x. Let [e.sub.x] stand for the identity element of [G.sub.x]. Then it is known that x[e.sub.x] = [e.sub.x]x and that the product belongs to [G.sub.x]. The latter fact allows one to consider the inverse of x[e.sub.x] in the group [G.sub.x]; we denote this inverse by [bar.x]. This defines the unary operation x [right arrow] [bar.x] on each epigroup; we call this operation pseudoinversion. Thus, epigroups can be treated as unary semigroups, that is, as algebras with two operations: multiplication and pseudoinversion, and we shall adopt this meaning of the term 'epigroup' throughout. Let E stand for the class of all epigroups.

A systematic study of epigroups as unary semigroups was initiated by Lev Shevrin in Shevrin (1994a,b, 2005). In particular, Shevrin suggested to investigate the collection of all unary semigroup identities holding in all epigroups, that is, the equational theory of E as a class of unary semigroups (i). The most fundamental questions about this theory are whether or not it is decidable and whether or not it is finitely axiomatizable.

Yet another motivation for studying unary identities of epigroups comes from the theory of finite semigroups. Every finite semigroup can be treated as an epigroup, and the unary operation of pseudoinversion is an implicit operation in the sense of Jan Reiterman Reiterman (1982), that is, it commutes with the homomorphisms between finite semigroups. Therefore, for each collection [SIGMA] of unary identities of epigroups, the class of all finite semigroups satisfying [SIGMA] is a pseudovariety. In fact, many important pseudovarieties can be defined by identities involving the operation of pseudoinversion (which within the realm of finite semigroups is usually denoted by x [right arrow] [x.sup.[omega]-1]) or the operation x [right arrow] [x.sup.[omega]] := [bar.x]x; see Almeida (1995) for plentiful examples.

We denote by [E.sub.fin] the class of all finite epigroups. Along with E and [E.sub.fin], among important classes of epigroups is the class [A.sub.fin] consisting of finite combinatorial (or aperiodic) semigroups. Recall that a semigroup is combinatorial if all its maximal subgroups are one-element.

At the end of the 1990s Ilya Zhil'tsov began to study the decidability problem for the equational theory of [A.sub.fin] (considered as a class of epigroups) along with a more general question. First results he obtained were published in Zhil'tsov (1999) and a full solution of the problem for [A.sub.fin] (found independently of Jon McCammond's solution in McCammond (2001)) was announced in Zhil'tsov (2000). The paper Zhil'tsov (2000) also contained similar results for the pseudovariety [E.sub.fin]. We collect these results in the following statement:

Theorem 1 The equational theory of the class E coincides with the equational theory of the class [E.sub.fin] and is decidable. The theory is not finitely based but has the following infinite identity basis:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Very unfortunately, soon after the announcement Zhil'tsov (2000) had appeared, Zhil'tsov died in a tragic accident and left no implementation of the statements indicated in Zhil'tsov (2000). It took us considerable effort to reconstruct all necessary steps of the proof. In Sections 2 and 3 we follow Zhil'tsov's plan outlined in Zhil'tsov (2000) quite closely while in Section 4 we choose a somewhat different way.

In Section 2 we introduce Zhil'tsov's concept of a Z-unary word. He suggested to consider words with not just one but countably many additional unary operations. In Section 3, we consider normal forms for Z-unary words and prove two of Zhil'tsov's propositions. First, it is possible to algorithmically construct the normal form. Second, there is an algorithm that, for two Z-words in normal form, returns their longest common prefix [suffix]. In particular, this means that there is an algorithm that decides whether the normal forms of given Z-unary words coincide. In Section 4 we consider epigroup terms as Z-unary words and show that an epigroup identity holds in each epigroup if and only if the normal form of the left-hand side of the identity coincides with the normal form of its right-hand side.

When the results forming this paper had already been obtained and the paper was being prepared for publication, the author learned about Jose Carlos Costa's preprint Costa (2013) also dealing with the equational theory of [E.sub.fin]; later Costa's paper Costa (2014) was published. Let us briefly comment on the relation between Costa (2014) and the present paper. Both papers provide algorithms to decide the equational theory of [E.sub.fin] and bases for the theory. However, the two algorithmS [union] Tilize essentially different approaches and their justifications come from different sources. The bases found in Costa (2014) and in the present paper are, of course, equivalent.

2 Z-unary words

2.1 Basic definitions

We fix an alphabet A, that is, a non-empty set which elements are referred to as letters. As usual, by [A.sup.+] we denote the free semigroup over A, that is, the set of all non-empty words over A which are multiplied by concatenation. We extend [A.sup.+] to a larger algebra that we denote by Z (A) and call the free Z-unary semigroup over A, the elements of Z (A) being called Z-unary words over A. For this we fix a symbol [omega] and define the notions of a Z-unary word and of its height by simultaneous induction as follows:

1) the empty word is a Z-unary word of height -[infinity];

2) every letter from A is a Z-unary word of height 0;

3) for every integer q [member of] Z and every Z-unary word [sigma] of height h, the expression [([sigma]).sup.[omega]+q] is a Z-unary word of height h + 1;

4) for every pair [[sigma].sub.1], [[sigma].sub.2] of Z-unary words of heights [h.sub.1] and respectively [h.sub.2], the expression [[sigma].sub.1][[sigma].sub.2] is a Z-unary word of height max{[h.sub.1], [h.sub.2]}.

For example, the expression

[([x.sup.[omega]-4]y[x.sup.[omega]+30]).sup.[omega]-1]x[y.sup.[omega]]

is a Z-unary word over {x, y} of height 2. This example also illustrates three natural conventions that we adopt throughout: we omit parentheses in expressions like [([sigma]).sup.[omega]+q] whenever [sigma] is just a letter and take the liberty to write [omega] instead of [omega] + 0 and [omega] - q instead of [omega] + (-q) for q being a positive integer.

We denote the height of [sigma] [member of] Z(A) by h([sigma]). It is easy to verify that every Z-unary word [sigma] of height h+1 with h [greater than or equal to] 0 can be uniquely represented as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where n [greater than or equal to] 1, h([[rho].sub.i]) = h for alli = 1,... , n, and h([[pi].sub.i]) [less than or equal to] h for all i = 0,..., n. We call (1) the height representation of [sigma].

We define the mapping [sigma] [??]|[sigma]| from the free Z-unary semigroup Z (A) into the ring Z[[omega]] of all polynomials in [omega] with integer coefficients as follows:

1) |[sigma] | := 0 if [sigma] is the empty word;

2) |[sigma]| := 1 whenever [sigma] is a letter from A;

3) |[[sigma].sup.[omega]+q]| := ([omega] + q)|[sigma]| for every integer q [member of] Z and every [sigma] [member of] Z(A);

4) |[sigma][tau]| := |[sigma]| + |[tau]| for all [sigma], [tau] [member of] Z (A).

We call |[sigma]| the length of the Z-unary word [sigma]. Observe that h([sigma]) is just is the degree deg |[sigma]| of the polynomial |[sigma]|. For two polynomials f,g [member of] Z [[omega]], we write f [greater than or equal to] g if the leading coefficient of the polynomial f - g is non-negative. Then |[sigma]| [greater than or equal to] 0 for every [sigma] [member of] Z( A).

We say that a Z-unary word [tau] is a prefix [resp. suffix] of [sigma] [member of] Z (A) if [sigma] = [tau][rho] [resp. [sigma] = [rho][tau]] for some [rho] [member of] Z (A). A Z-unary word [tau] is a factor of [sigma] if [sigma] = [[rho].sub.1][tau][[rho].sub.2] for some [[rho].sub.1], [[rho].sub.2] [member of] Z (A) and it is a power of [sigma] if [tau] = [[sigma].sup.n] for some n [greater than or equal to] 2. Likewise, Z-unary words of the form [[sigma].sup.[omega]+q], where q is an integer, are called [omega]-powers of [sigma]. Observe that the free Z-unary semigroup Z (A) considered as a semigroup is just the free monoid generated by A and all [omega]-powers.

2.2 Singular words

Consider the fully invariant congruence S on the free Z-unary semigroup Z (A) generated by the pairs

([x.sup.[omega]+q], x[x.sup.[omega]+q-1)], (2)

([x.sup.[omega]+q], [x.sup.[omega]+q-1]x), (3)

[(x(yx).sup.[omega]+q], [(xy).sup.[omega]+q]x), (4)

where q runs over Z.

By a singular word or, shortly, a sword we mean an S-class. The class corresponding to a given Z-unary word [sigma] is denoted by [[sigma].sup.s]. Notice that if [sigma] is an ordinary word, that is, [sigma] [member of] [A.sup.+], then [[sigma].sup.s] = {[sigma]}. The quotient algebra Z(A)/S of all swords is denoted by Sing (A).

Example 1 (Zhil'tsov) Consider the Z-unary word x[(xyz).sup.[omega]-5]xy[(zx).sup.[omega]+4]zz of height 1 and of length 5[omega] - 2. We can represent it by the following picture:

[FIGURE 1 OMITTED]

Here the [omega]-powers [(xyz).sup.[omega]-5] and [(zx).sup.[omega]+4] are represented by the circles labeled xyz and zx with encircled numbers -5 and 4 respectively. Now we draw the analogous pictures for three further Z-unary words that belong to the same S-class. These pictures illustrate three basic transformations that one can perform on a Z-unary word without changing its S-class.

* One can "unwind" n copies of a circle to the left or the right side of the circle, simultaneously decreasing its encircled number by n - in Fig. 2 this transformation is applied to the circle labeled zx in Fig. 1 with n = 2. This corresponds to n applications of either (2) or (3) from left to right.

* One can "wind up" (if it is possible) n copies of a circle from the left or the right side of the circle, simultaneously increasing its encircled number by n - in Fig. 3 this transformation is applied to the circle labeled xyz in Fig. 2 with n = 1. This corresponds to n applications of either (2) or (3) from right to left.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

* One can "roll" a circle to the left (right) side if some suffix (resp. prefix) of the circle's label is written before (resp. after) the circle--in Fig. 4 this transformation is applied to the circle labeled zx in Fig. 3. This corresponds to an application of (4).

Thus, any sword can be considered as an ordinary word with some attached "singularities" ([omega]-powers that may contain further [omega]-powers etc.) that can move along the word. This explains our terminology.

We refer to the basic transformations illustrated in Example 1 as S-transformations. Each S-transformation involves a certain [omega]-power which we call the site of the transformation. Clearly, two Z-unary words belong to the same S-class if and only if one can obtain each of these words form the other by a suitable sequence of S-transformations.

Notice that, due to the definition of the congruence S, the following conditions hold for all Z-unary words [sigma], [tau] in the same S-class:

* [sigma] and [tau] have the same height;

* [sigma] and [tau] have the same length.

Thus, we can well define the height and the length of a sword [[sigma].sup.S] as the height and respectively the length of [sigma]. We can also speak about a height representation of a sword; observe, however, that in contrast to Z-unary words, a sword may have several height representations.

We say that a sword [[tau].sup.S] is a prefix [suffix, factor] of a sword [[sigma].sup.S] if, for some Z-unary words [tau]', [sigma]' such that [([tau]').sup.S] = [[tau].sup.S] and [([sigma]').sup.S] = [[sigma].sup.S], the Z-unary word [tau]' is a prefix [resp. suffix, factor] of [sigma]'. In the same way, the notions of a power and of an [omega]-power extend to swords.

As we will see, the algebra Sing(A) considered as a semigroup inherits several important properties from the free semigroup. Of course, there are some differences too. For instance, each sword of height more than zero has infinitely many factors. Further, for every ordinary word w and every integer t such that 0 [less than or equal to] t [less than or equal to] |w|, there exists a prefix of w with length t. This is not true in general swords: for example, the sword [([([x.sup.2]).sup.[omega]]).sup.S] has no prefix of length [omega].

Lemma 1 There is an algorithm that, given an arbitrary sword [sigma] and a polynomial f([omega]) [member of] Z[w] such that the leading coefficient of|[sigma]| - f([omega]) is non-negative, decides whether [sigma] has a prefix of length f([omega]). If the answer is positive, the algorithm constructs swords [x.sup.S], [y.sup.S] such that [[sigma].sup.S] = [x.sup.S][y.sup.S] and |x| = f([omega]).

Proof: We induct on the height of [sigma]. As we have noticed prior to the formulation of the lemma, its statement holds for ordinary words and hence for swords of height 0.

Let h([sigma]) = h + 1 and let (1) be the height representation of [sigma]. Since f([omega]) [less than or equal to] |[sigma]|, there is an index k such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(If deg f([omega]) < h + 1, then k = 0 and the above inequality takes the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (In the case where k = 0, we let g([omega]) = f([omega]).) Clearly, [[sigma].sup.S] has a prefix of length f([omega]) if and only if the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a prefix of length g([omega]).

First suppose that deg g([omega]) < h + 1. Then it is possible to choose a positive integer m such that the leading coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is non-negative, and we are in a position to apply the induction hypothesis to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the polynomial g([omega]). If the answer is positive and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the required swords are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now suppose that deg g([omega]) = h + 1. It is easy to see that if the required prefix exists then it has the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some integer t [less than or equal to] [q.sub.k+1] and some prefix [eta] of the Z-unary word [[rho].sub.k+1]. Since h([[pi].sub.k]) [less than or equal to] h and h([eta]) [less than or equal to] h, we conclude that, by the definition of the length, the leading coefficients of the polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and g([omega]) must coincide. If this holds, then we choose an integer s < [q.sub.k+1] such that the leading coefficient of the polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is non-negative. Since deg g'([omega]) < h + 1, we can apply the induction hypothesis to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the polynomial g'([omega]), obtaining either a negative answer or a decomposition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the required prefix is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Lemma 2 1. Sing(A) is a 3-trivial cancellative semigroup;

2. The set of all prefixes [suffixes] of a sword is linearly ordered by right [resp. left] division.

Proof: Let us start with the proof of the cancelation property. Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This implies [([sigma][tau]1).sup.S] = [([sigma][[tau].sub.2]).sup.S]. Therefore there exists a sequence of Z-unary words [sigma][[tau].sub.1] = [[eta].sub.1], [[eta].sub.2],... , [[eta].sub.n] = [sigma][[tau].sub.2] such that for each i = 1,..., n - 1, the word [[eta].sub.i+1] can be obtained from the word [[eta].sub.i] by one of the S-transformations: "unwinding", "winding up", or "rolling". We will construct two sequences of Z-unary words [[alpha].sub.1],...,[[alpha].sub.n] and [[beta].sub.1],..., [[beta].sub.n] with the following properties:

(i) [[alpha].sub.1] = [sigma], [[beta].sub.1] = [[tau].sub.1];

(ii) for each i = 1,..., n - 1, one can pass from [[alpha].sub.i] to [[alpha].sub.i+1] and from [[beta].sub.i] to [[beta].sub.i+1] by a sequence of S-transformations;

(iii) for each i = 1,..., n, the Z-unary word [[alpha].sub.i][[beta].sub.i] can be obtained from [[eta].sub.i] by applying only "unwinding" S-transformations.

This will imply the desired conclusion [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Indeed, by (i) and (ii), we have [sigma] = [[alpha].sub.1] S [[alpha].sub.n] and [[tau].sub.1] = [[beta].sub.1] S [[beta].sub.n] whence, in particular, |[sigma]| = |[[alpha].sub.n]|. By (iii), [[alpha].sub.n][[beta].sub.n] can be obtained from [[eta].sub.n] = [sigma][[tau].sub.2] by "unwinding" S-transformations only. The definition of an "unwinding" S-transformation implies that if such a transformation is applied to a product of two Z-unary words, its site is contained in one of the factors. Thus, we conclude that [[alpha].sub.n][[beta].sub.n] = [gamma][delta], where [gamma] and [delta] are obtained by some "unwinding" S-transformations from [sigma] and [[tau].sub.2] respectively. In particular, [sigma] S [gamma] and [[tau].sub.2] S [delta]. Since |[gamma]| = |[sigma]| = |[[alpha].sub.n]|, we have [gamma] = [[alpha].sub.n] whence [delta] = [[beta].sub.n]. This yields [[tau].sub.1] S [[beta].sub.n] = [delta] S [[tau].sub.2] and [[tau].sub.1] S [[tau].sub.2], as required.

Thus, it remains to construct the sequences [[alpha].sub.1],..., [[alpha].sub.n] and [[beta].sub.1],..., [[beta].sub.n] satisfying (i)-(iii). We proceed by induction, using (i) as the induction basis. Suppose that the Z-unary words [[alpha].sub.i] and [[beta].sub.i] have already been defined. If the S-transformation [PHI] applied to obtain [[eta].sub.i+1] from [eta]i is of the type "winding up", we let [[alpha].sub.i+1] = [[alpha].sub.i], [[beta].sub.i+1] = [[beta].sub.i]. If [PHI] is of the type "unwinding", one of the two possibilities occur: either [PHI] is one of the S-transformations employed to convert [[eta].sub.i] into [[alpha].sub.i][[beta].sub.i] or not. In the former case we again let [[alpha].sub.i+1] = [[alpha].sub.i], [[beta].sub.i+1] = [beta]i. In the latter case, the site of [PHI] persists in [[alpha].sub.i][[beta].sub.i] and, as already mentioned, it is located within one of the factors [[alpha].sub.i] or [[beta].sub.i]. If the site lies within [[alpha].sub.i], we let [[alpha].sub.i+]1 be the result of applying [PHI] to [[alpha].sub.i] and let [[beta].sub.i+]1 = [beta]i; otherwise we let [[alpha].sub.i+]1 = [[alpha].sub.i] and let [[beta].sub.i+1] be the result of applying [PHI] to [[beta].sub.i].

Now let [PHI] be of the type "rolling". By symmetry, we may assume that [PHI] corresponds to an application of (4) from right to left, that is, the site [(xy).sup.[omega]+q] of [PHI] is followed by x in [[eta].sub.i] and "rolls" to the right producing x[(yx).sup.[omega]+q] in [[eta].sub.i+1]. Since [[alpha].sub.i][[beta].sub.i] is obtained from [[eta].sub.i] by "unwinding" S-transformations, [[alpha].sub.i][[beta].sub.i] may contain several copies of the site of [PHI]--for illustration, if, say, [[eta].sub.i] = [(z[(xy).sup.[omega]+q]x).sup.[omega]+r], then unwinding the external [omega]-power gives Z-unary words of the form [(z[(xy).sup.[omega]+q]x).sup.s][(z[(xy).sup.[omega]+q]x).sup.[omega]+r-s-t][(z[(xy).sup.[omega]+q]x).sup.t], with s +t + 1 occurrences of the site. We apply [PHI] to all copies of [(xy).sup.[omega]+q]x that occur within [[alpha].sub.i] or [[beta].sub.i]. Besides that, it may happen that some copies of the site have undergone unwinding themselves, resulting in a Z-unary word of the form [xi] = [(xy).sup.r] [(xy).sup.[omega]+q-r-s] [(xy).sup.s]x. Whenever such a [xi] lies entirely within [[alpha].sub.i] or [[beta].sub.i], we substitute it by x[(yx).sup.r] [(yx).sup.[omega]+q-r-s] [(yx).sup.s]--clearly, this amounts to "rolling" of [(xy).sup.[omega]+q-r-s] to the right. If [xi] occurs on the junction of [[alpha].sub.i] and [[beta].sub.i], we can basically do the same except for the only case where [(xy).sup.r][(xy).sup.[omega]+q-r-s] is a suffix of [[alpha].sub.i] while [(xy).sup.s]x is a prefix of [[beta].sub.i] because in this case we cannot "roll" [(xy).sup.[omega]+q-r-s] to the right within [[alpha].sub.i]. In this remaining case, when passing from [[alpha].sub.i] to [[alpha].sub.i+1], we substitute [(xy).sup.r] [(xy).sup.[omega]+q-r-s] by x[(yx).sup.r] [(yx).sup.[omega]+q-r-s-1]y. This concludes the induction step.

Now let us show that Sing(A) is [??]-trivial. Indeed, assume that some swords [[alpha].sup.S], [[beta].sup.S] are [??]-related. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [[sigma].sub.1],[[sigma].sub.2],[[tau].sub.1],[[tau].sub.2] [member of] Z (A). We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whence |[[sigma].sub.1] | = |[[sigma].sub.2]| = |[[tau].sub.1]| = |[[tau].sub.2]| = 0 and all these Z-unary words must be empty. Hence [[alpha].sup.S] = [[beta].sup.S].

The [??]-triviality of the semigroup Sing(A) implies that the relations of right and left division are partial orders on Sing(A). We aim to show that their restrictions to the set of all prefixes [suffixes] of a fixed sword [[sigma].sup.S] are linear orders. By symmetry, it suffices to consider right division only. Thus, suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and |[[tau].sub.1]| < |[tau]2|. Since [[tau].sub.1][[rho].sub.1] S [[tau].sub.2][[rho].sub.2], the sword [([[tau].sub.2][[rho].sub.2]).sup.S] has aprefix of length |[[tau].sub.1]| that should be also a prefix of the sword [([[tau].sub.2]).sup.S]. Hence, using the algorithm of Lemma 1, we can find two swords [x.sup.S] and [y.sup.S] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and |x| = |[[tau].sub.1]|.

Since [[tau].sub.1][[rho].sub.1] S xy[[rho].sub.2], there exists a sequence of Z-unary words [[eta].sub.1] = [[tau].sub.1][[rho].sub.1], [[eta].sub.2],..., [[eta].sub.n] = xy[[rho].sub.2] such that [[eta].sub.i+1] can be obtained from [[eta].sub.i] by an application of a suitable S-transformation for each i = 1,... ,n - 1. Now we follow the proof of the cancelation property above and construct two sequences of Z-unary words [[alpha].sub.1],...,[[alpha].sub.n] and [[beta].sub.1],..., [[beta].sub.n] such that

(i) [[alpha].sub.1] = [[tau].sub.1], [[beta].sub.1] = [[rho].sub.1];

(ii) for each i = 1,..., n - 1, one can pass from [[alpha].sub.i] to [[alpha].sub.i+1] and from [[beta].sub.i] to [[beta].sub.i+1] by a sequence of S-transformations;

(iii) for each i = 1,..., n, the Z-unary word [[alpha].sub.i][[beta].sub.i] can be obtained from [[eta].sub.i] by applying only "unwinding" S-transformations.

Then the same argument as the one we have utilized in the proof of the cancelation property shows that [[tau].sub.1] = [[alpha].sub.1] S [[alpha].sub.n] S x whence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] divides [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on the right. []

3 Normal swords

3.1 Overview

In this section we introduce a rewriting system that plays a key role for the decidability question. Let R denote the rewriting system on the free Z-unary semigroup Z (A) consisting of the rules

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

for all x [member of] Z (A), all r, q [member of] Z, and all n [greater than or equal to] 2. Observe that all these rules are length-decreasing; the rule (7) is also height-decreasing while (5) and (6) do not change the height. The rewriting system R induces the "quotient" rewriting system R/S on the quotient semigroup Sing(A) = Z(A)/S as follows: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if there exist Z-unary words [sigma] and [tau] such that [[alpha].sup.S] = [[sigma].sup.S], [[beta].sup.S] = [[tau].sup.S], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By (R/S)* we denote the reflexive and transitive closure of R/S.

A normal sword (or an R/S-irreducible sword) is a sword [[alpha].sup.S] such that there is no sword [[beta].sup.S] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Observe that every factor of a normal sword is also normal. A sword [[alpha].sup.S] is called fully normal if its square [([[alpha].sup.S]).sup.2] is normal. It is easy to see that then [([[alpha].sup.S]).sup.n] is normal for all n [greater than or equal to] 2.

Any normal sword which is (R/S)* -related to a given sword [[sigma].sup.S] is said to be a normal form of [[sigma].sup.S]. We stress that at this point we claim no uniqueness nor confluence: a sword may have several normal forms.

Up to now, we have always tried to differentiate between a sword (i.e., an S-class) and a Z-unary word representing this S-class. In the sequel, in order to lighten the notation, we allow ourselves to omit the [superscript.sup.S] so that a sword, say, [[alpha].sup.S] may be denoted by just [alpha].

This definition of a normal sword implies that such a sword contains no factors of the forms [x.sup.[omega]+r][x.sup.[omega]+q], [([x.sup.n]).sup.[omega]+q], [([x.sup.[omega]+r]).sup.[omega]+q]. Notice also that if a sword is fully normal, then it is obviously normal and cannot have the form [x.sup.[omega]+m] nor [x.sup.[omega]+r]y[x.sup.[omega]+q]. Clearly, all ordinary words are fully normal.

The main goal of this section is to prove the two following propositions.

Proposition 1 There exists an algorithm that, given a sword [sigma] of height h, returns a normal form of [sigma].

Proposition 2 There exists an algorithm that, given two normal swords of height at most h, returns their longest common prefix.

We have included the parameter h in the formulations of Propositions 1 and 2 because we are going to prove these propositions, along with Lemmas 3-7 formulated below, by simultaneous induction on h. All these statements obviously hold for swords of height 0 (i.e., for ordinary words), and we will assume that they hold true for all swords of height h - 1.

We will also use the following corollary of Proposition 2:

Corollary 1 There is an algorithm that checks whether or not two given normal swords are equal.

Proof: Let [sigma], [tau] be normal swords. Using the algorithm of Proposition 2, we find their longest common prefix [rho]. Clearly, [sigma] = [tau] if and only if [sigma] = [rho] and [tau] = [rho], and the two latter equalities are equivalent to the equalities |[sigma]| = |[rho]| and respectively |[tau]| = |[rho]| in view of Lemma 2. []

3.2 Periodic normal swords

We will need two auxiliary facts similar to well-known properties of ordinary words. Given a sword [tau], a sword [sigma] is called [tau]-periodic if [sigma] is a power or an [omega]-power of [tau].

Lemma 3 Let [sigma], [tau] be non-empty normal swords of height at most h and [tau][sigma] = [sigma][tau]. Then there exists a fully normal sword [pi] such that both [tau] and [sigma] are [pi]-periodic. If besides that, [sigma] and [tau] are fully normal, then h([sigma]) = h([tau]) = h([pi]) and [sigma] = [[pi].sup.n1], [tau] = [[pi].sup.n2] for some positive integers [n.sub.1],[n.sub.2].

Proof: By symmetry, we may assume that |[sigma]| [greater than or equal to] |[tau]|. Observe that since [sigma][tau] = [tau][sigma], the sword [tau] is a prefix of [sigma] by item 2 of Lemma 2. Therefore, there exists a sword [sigma]' such that [sigma] = [tau][sigma]' whence [tau][sigma]'[tau] = [sigma][tau] = [tau][sigma] = [[tau].sup.2][sigma]'. Since [[tau].sup.2] is a prefix of a normal sword, it is normal whence [tau] is fully normal. Further, by item 1 of Lemma 2, we can cancel [tau] in the equality [tau][sigma]'[tau] = [[tau].sup.2][sigma]', thus getting [sigma]'[tau] = [tau][sigma]'.

First consider the case h([sigma]) > h([tau]). Then h([sigma]') > h([tau]) whence |[sigma]'| > |[tau]|. Arguing as in the preceding paragraph, we see that [tau] is a prefix of [sigma]' and there exists a sword [sigma]" of height h([sigma]) such that [sigma]"[tau] = [tau][sigma]", and so on. Therefore, for any positive integer m, the sword [[tau].sup.m] is a prefix of the sword [sigma]. It is clear this is only possible if [sigma] has some [omega]-power of [tau] as a prefix. Therefore, we may assume that [sigma] = [[tau].sup.[omega]+k][[sigma].sub.1] for some integer k and some sword [[sigma].sub.1].

Suppose that h([[sigma].sub.1]) = h([sigma]). Observe that [[tau].sup.[omega]+k][sigma]1[tau] = [sigma][tau] = [tau][sigma] = [[tau].sup.[omega]+k+1][[sigma].sub.1]. Using item 1 of Lemma 2, we conclude that [[sigma].sub.1][tau] = [tau][[sigma].sub.1], and we can repeat the same steps as before to obtain that [[sigma].sub.1] = [[tau].sup.[omega]+l][[sigma].sub.2] for some integer l and some sword [[sigma].sub.1]. Then, however, the sword [sigma] = [[tau].sup.[omega]+k][[tau].sup.[omega]+l][[sigma].sub.2] would not be normal, a contradiction.

Hence h([[sigma].sub.1]) < h([sigma]). If [[sigma].sub.1] is not empty, we can apply the induction hypothesis to the swords [[sigma].sub.1] and [tau] whose height is strictly less than h. There exists a fully normal sword [pi] such that both [[sigma].sub.1] and [tau] are [pi]-periodic but then [sigma] = [[tau].sup.[omega]+k][[sigma].sub.1] could not be normal, a contradiction again. Thus, [[sigma].sub.1] is empty, whence [sigma] = [[tau].sup.[omega]+k] is an [omega]-power of the fully normal sword [tau] and the first statement of the lemma holds true.

Assume now that h([sigma]) = h([tau]). Then |[sigma]| = [l.sub.1][[omega].sup.h] + [g.sub.1](w), |[tau]| = [l.sub.2][[omega].sup.h] + [g.sub.2]([omega]), where deg([g.sub.i]) < h for i = 1,2. We proceed by induction on max{[l.sub.1], [I.sub.2]}.

If [l.sub.1] = [l.sub.2] (in particular, if max{[l.sub.1], [l.sub.2]} = 1), the sword [sigma]' such that [sigma] = [tau][sigma]' = [sigma]'[tau] has height less than h, and this leads to the case just considered. We then obtain that there is a fully normal sword [pi] such that [tau] = [[pi].sup.[omega]+k] and [sigma]' = [[pi].sup.m] for some integers k, m, and thus, [sigma] = [[pi].sup.[omega]+k+m]. If [l.sub.1] = [l.sub.2], we apply the induction hypothesis to the pair [sigma]',[tau] to obtain the required property.

The second statement of the lemma trivially follows from the definition of a fully normal sword. []

Lemma 4 Let x and y be fully normal swords. Suppose that |x| [greater than or equal to] |y| and [x.sup.2] is a prefix [suffix] of some y-periodic sword. Then there exists a fully normal sword z such that x and y are powers of z. If besides that, some [omega]-powers of x and y are prefixes [suffixes] of a normal sword, then x = y.

Proof: Since x2 is a prefix of a power or an [omega] -power of y and |x| [greater than or equal to] |y|, a power or an [omega] -power of y should be a prefix of x. In the latter case there are swords [y.sub.1], [y.sub.2] and a prefix [y.sub.3] of y such that y = [y.sub.1][y.sub.2] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [r.sub.1],[r.sub.2] [member of] Z whence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We see that x is not fully normal, a contradiction.

If a power of y but no [omega]-power of y is a prefix of x, then there exist swords [y.sub.1], [y.sub.2] and a prefix [y.sub.3] of y such that [y.sub.1][y.sub.2] = y and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since both [y.sub.1][y.sub.2] and [y.sub.2][y.sub.1] are prefixes of x and have the same length, we conclude that [y.sub.1][y.sub.2] = [y.sub.2][y.sub.1]. Since y is fully normal, by Lemma 3 we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [k.sub.1],[k.sub.2] [greater than or equal to] 1 and some fully normal sword z. Hence x and y are powers of z.

The second statement of the lemma immediately follows from the fact that, because of the rule (6), the only power of z that can occur as a factor in a normal sword is z itself. Hence, x = z and y = z. []

3.3 Normalization

Our algorithm that constructs a normal form of an arbitrary sword will repeatedly invoke two procedures. Recall that every sword of height h can be represented as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where each of the swords [[pi].sub.0], [[pi].sub.1],..., [[pi].sub.n], [[rho].sub.1],..., [[rho].sub.n] has height less than h. Therefore it suffices to exhibit a procedure that produces a normal form for a given sword being an [omega]-power of a normal swords and a procedure that produces a normal form for the product of two given normal swords.

We start with the latter procedure. First of all, observe that the product of two normal swords may indeed fail to be normal. For example, if [[sigma].sub.1] = [([xz.sup.[omega]+2]).sup.[omega]] and [[sigma].sub.2] = [z.sup.[omega]-5], then the product [[sigma].sub.1][[sigma].sub.2] = [([xz.sup.[omega]+2]).sup.[omega]][z.sup.[omega]-5] is not normal because it is equal (as a sword) to [([xz.sup.[omega]+2]).sup.[omega]-1][xz.sup.[omega]+2][z.sup.[omega]-5]. One can obtain a normal form of [([xz.sup.[omega]+2]).sup.[omega]-1][xz.sup.[omega]+2][z.sup.[omega]-5] by applying to it just one R/S-transition of the form (5), thus producing [([xz.sup.[omega]+2]).sup.[omega] - 1][xz.sup.[omega]-3]

Actually, the situation demonstrated by the above example is generic. By the definition of a normal sword, it is clear that the product of two normal swords is not normal if and only if it has a factor of the form [y.sup.[omega]+r][y.sup.[omega]+q]. Thus, the fact that [[sigma].sub.1] and [[sigma].sub.2] are normal while [sigma]1[sigma]2 is not is equivalent to the existence of a sword y such that [[sigma].sub.1] has a suffix and [[sigma].sub.2] has a prefix that are [omega]-powers of y. Obviously, if such a sword y exists, it should be fully normal and by Lemma 4 it is unique. We refer to y as to the overlap between [[sigma].sub.1] and[[sigma].sub.2].

Lemma 5 Let [[sigma].sub.1], [[sigma].sub.2] be two normal swords of height no more than h. There exists an algorithm that decides whether the product [[sigma].sub.1][[sigma].sub.2] is in normal form. If the product is not normal, the algorithm finds the overlap between [[sigma].sub.1] and [[sigma].sub.2] and constructs a normal form for the product.

Proof: First, we describe an algorithm that, given two normal swords [[sigma].sub.1], [[sigma].sub.2] of height h, decides if they have an overlap of height h - 1, and in the case where the answer is positive, finds the overlap and constructs a normal form for [[sigma].sub.1] [[sigma].sub.2]. Since the algorithm will be repeatedly invoked in the rest of the proof, it is convenient to give it a name. So, let us call this algorithm TO (from "tall overlap").

We start with representing the given swords as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

where h([[rho].sub.1]) = h([[rho].sub.2]) = h - 1 and h([[pi].sub.1]), h([[pi].sub.2]) [less than or equal to] h - 1. If [sigma]1 has a suffix that is an [omega]-power of some sword of height h - 1, then the suffix is of height h, and hence, it has to involve some [omega]-power of [[rho].sub.1] as a factor. Clearly, this is only possible if [[rho].sub.1] = [[pi].sub.1][[rho]'.sub.1] for some sword [[rho]'.sub.1], and we can decide whether or not the latter equality holds true by applying the algorithm of Proposition 2 to the swords [[pi].sub.1] and [[rho].sub.1] to find their longest common prefix and then deciding whether or not this prefix is equal to [pi]1. If the answer is positive, we can rewrite the sword [sigma]1 (by "rolling" [([[pi].sub.1][[rho]'.sub.1]).sup.[omega]+q1] to the right) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly, if [sigma]2 has a prefix that is an [omega]-power of some sword of height h - 1, then the prefix is of height h and has some [omega]-power of [[rho].sub.2] as a factor. This is only possible if [[rho].sub.2] = [[rho]'.sub.2][[pi].sub.2] for some sword [[rho]'.sub.2], which can be verified by applying the "dual" of the algorithm of Proposition 2. If the answer is positive, we can rewrite the sword [sigma]2 (by "rolling" [([[rho]'.sub.2][[pi].sub.2]).sup.[omega]+q2] to the left) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now it remains to verify whether or not the swords [[rho]'.sub.1][[pi].sub.1] and [[pi].sub.2][[rho].sub.2] of height h - 1 are equal. If the answer is negative, [sigma]1 and [sigma]2 have no overlap of height h - 1. Otherwise, the sword y = [[rho]'.sub.1][[pi].sub.1] = [[pi].sub.2][[rho]'.sub.2] is the overlap of height h - 1 between [[sigma].sub.1] and [[sigma].sub.2] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Applying an R/S-transition of the form (5), we reduce it to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We are going to prove that [tau] is normal, and thus, it is a normal form for the product [[sigma].sub.1][[sigma].sub.2]. Arguing by contradiction, assume that [tau] is not normal. Then there should be the overlap z, say, between either [[sigma]'.sub.1][[pi].sub.1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[pi].sub.2][[sigma].sub.2]. Since the height of [tau] is h, the height of z is at most h - 1 whence z contains no [omega]-power of y as a prefix nor as a suffix. Then Lemma 4 easily implies that z = y, but this leads to a contradiction: if [[sigma]'.sub.1] [[pi].sub.1] has an [omega]-power of y as a suffix, the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] could not be normal, andif [[pi].sub.2][[sigma]'.sub.2] has an [omega]-power of y as a prefix, the same conclusion applies to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now assume that the algorithm TO has revealed that the swords [sigma]1 and [sigma]2 have no overlap of height h - 1. Then we have to check whether they have an overlap of lesser height. For this, we again represent the swords in the form (8) and apply the algorithm of Lemma 5 to the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which are both of height less than h. If there is no overlap between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there also is no overlap of height less than h - 1 between [sigma]1 and [sigma]2 and the product [[sigma].sub.1][[sigma].sub.2] is in normal form. Otherwise, the algorithm finds the overlap between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Denoting the overlap by y, we can represent these swords as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some [r.sub.1],[r.sub.2] [member of] Z. Consider the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] obtained from [[sigma].sub.1][[sigma].sub.2] by an R/S-transition of the form (5). Clearly, to check whether [theta] is normal amounts to examining overlaps between the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or between the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In contrast to the situation in the previous paragraph, here the overlaps may exist, and it appears to make sense to illustrate this phenomenon by an example.

Thus, consider the normal swords [tau]1 = [([x.sup.[omega]]y).sup.[omega]+1][x.sup.[omega]] and [[tau].sup.2] = [([x.sup.[omega]]y).sup.[omega]-2] of height 2. They have no overlap of height 1, but do have the overlap of height 0, namely, x: this becomes obvious if we rewrite [[tau].sub.2] as [x.sup.[omega]]y[([x.sup.[omega]]y).sup.[omega]-3]. Applying an R/S-transition of the form (5) to the product [tau]1[tau]2, we obtain the sword [([x.sup.[omega]]y).sup.[omega]+1][x.sup.[omega]]y[([x.sup.[omega]]y).sup.[omega]-3], and we see that the swords [([x.sup.[omega]]y).sup.[omega]+1] and [x.sup.[omega]]y[([x.sup.[omega]]y).sup.[omega]-3] = [([x.sup.[omega]]y).sup.[omega]-2] have the overlap [x.sup.[omega]]y, this time of height 1. Resolving the overlap with yet another transition of the form (5), we finally obtain the normal sword [([x.sup.[omega]]y).sup.[omega]-1] as a normal form for [[tau].sub.1][[tau].sub.2].

Observe that the above example illustrates not only the difficulty we encounter but also a way to overcome it: since the new overlap has height h([[tau].sub.1]) - 1, it can be found by the algorithm TO. Mutatis mutandis, this idea works also in the general case.

We return to the proof. Recall that we have to decide if there are overlaps between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. First, we apply TO to decide if there are overlaps of height h - 1, and in the case where the answer is positive, to construct a normal form for the sword [theta], which will be also a normal form for [[sigma].sub.1][[sigma].sub.2]. Suppose that TO has found no overlaps of height h- 1. Then we apply the algorithm of Lemma 5 to the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or to the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which are all of height less than h. If no overlaps are found, then there are no overlaps of height less than h - 1 between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] nor between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the sword [theta] is normal. Suppose that the algorithm has found the overlap z, say, between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If z has no [omega]-power of y as a prefix nor as a suffix, then Lemma 4 implies that z = y, and this leads to a contradiction: if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has an [omega]-power of y as a suffix, the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] could not be normal, and if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has an [omega]-power of y as a prefix, the same conclusion applies to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, z has no [omega]-power of y as a prefix or as a suffix whence h(y) < h(z) < h - 1. Now we apply the same sequence of arguments to z, etc. Clearly, each step of the described process deals with some sword [theta] obtained from [[sigma].sub.1][[sigma].sub.2] by a sequence of R/S-transitions and leads to exactly one of the three following results:

1. TO finds the overlap of height h - 1, resolves it in [theta], and returns a normal form for [[sigma].sub.1][[sigma].sub.2].

2. TO finds no overlap of height h - 1, and the algorithm of Lemma 5 applied to suitable words of height less than h finds no overlap of height less than h - 1, and therefore, [theta] constitutes a normal formfor [[sigma].sub.1][[sigma].sub.2].

3. TO finds no overlap of height h - 1, but the algorithm of Lemma 5 applied to suitable words of height less than h finds the overlap whose height is less than h-1 but greater than the height of the overlap found in the previous step. In this case we resolve the overlap in [theta] and pass to the next step.

It is clear that the number of steps of our process does not exceed h, and therefore, it will eventually return a normal form for [[sigma].sub.1][[sigma].sub.2].

It remains to analyze the situation where one of the swords [sigma]1 and [sigma]1 is of height less than h while the other has height h. (In the case where both h([[sigma].sub.1]) < h and h([sigma]2) < h, the induction hypothesis applies immediately.) The argument is similar to that described above but simpler because there is no need to invoke the algorithm TO-one of the swords is of height less than h, no overlap of height h - 1 is possible. By symmetry, we may suppose that h([[sigma].sub.1]) < h and h([[sigma].sub.2]) = h. Then we can represent [[sigma].sub.2] as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where h([[rho].sub.2]) = h - 1, h([[pi].sub.2]) [less than or equal to] h - 1. We apply the algorithm of Lemma 5 to the swords [[sigma].sub.1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which are both of height less than h. If there is no overlap between [sigma]1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there also is no overlap between [[sigma].sub.1] and [[sigma].sub.2] and the product [[sigma].sub.1][[sigma].sub.2] is in normal form. Otherwise, the algorithm finds the overlap between [sigma]1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Denoting the overlap by y, we can represent these swords as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some [r.sub.1], [r.sub.2] [member of] Z. Consider the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] obtained from [[sigma].sub.1][[sigma].sub.2] by an R/S-transition of the form (5). Clearly, to check whether [theta] is normal amounts to examining the overlaps between the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and between the swords [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] For this, we apply the algorithm of Lemma 5 to two pairs of swords: [[sigma]".sub.1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which swords are all of height less than h. If no overlaps have been discovered, the sword [theta] is normal and thus constitutes a normal form for the product [[sigma].sub.1][[sigma].sub.2]. If the overlap z, say, has been found, then the same argument as above shows that h(z) > h(y). We apply the same arguments to z, etc. The described process will eventually stop since the height of overlaps increases on each step but cannot reach h - 1. []

Now we study how to construct a normal form for the [omega]-power of a normal sword.

Lemma 6 Let [rho] be a normal sword of height h - 1. There is an algorithm that reduces the sword [[rho].sup.[omega]+q] either to a normal sword of height less than h or to a sword of the form [[alpha].sub.1][[beta].sup.[omega]+t][alpha]2 in which h([[alpha].sub.1]), h([alpha]2) [less than or equal to] h - 1, h([beta]) = h - 1, and the sword [[beta].sup.[omega]+t] is normal.

Proof: Assume that [[rho].sup.[omega]+q] is not normal. This means that an R/S-transition can be applied to the sword. Depending on the form of the transition, one of the three following cases occurs:

1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [m.sub.1], [m.sub.2] [member of] Z and some non-empty x' (the sword x' cannot be empty since [rho] is normal);

2) [rho] = [x.sup.n] for some integer n [greater than or equal to] 2;

3) [rho] = [x.sup.[omega]+m] for some integer m.

We apply the algorithm of Lemma 7 to the normal sword [rho] of height h - 1 to check whether one of the cases 2) or 3) occurs, and if it does, to find a corresponding fully normal sword x. We may additionally assume that x [not equal to] [y.sup.p] for any integer p [greater than or equal to] 2: in case 2) such an x is the sword of minimum length returned by the algorithm while in case 3) this holds automatically since [rho] is normal. Then [[rho].sup.[omega]+q] can be reduced to [x.sup.[omega]+nq] in case 2) or to [x.sup.[omega]+mq] in case 3) and either of these two [omega]-powers is easily seen to be normal.

In the remaining case 1), the sword [rho] must have a proper overlap with itself. We can check if this indeed happens by invoking the algorithm of Lemma 5 since the height of [rho] is less than h. Moreover, if the overlap exists, it is unique and fully normal, and the algorithm finds it. Thus, assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some fully normal sword [x.sub.0] and some [m.sub.1], [m.sub.2] [greater than or equal to] Z. Then the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can bereducedto the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is normal because any R/S-transition applicable to [[rho].sub.1] could have been applied also to [rho] while [rho] is normal. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is normal, we are done as we can put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [beta] = [[rho].sub.1].

Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not normal. Then one of the above cases 1)-3) takes place for [[rho].sub.1]. We already have seen how to handle case 2): we can reduce [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to its normal form being an [omega]-power of a fully normal word of height less than h. Substituting this normal form for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] produces a sword of the desired form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In case 3) there is a fully normal sword [x.sub.1] of height less than h - 1 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some integer l. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and we can apply an R/S-reduction of the form (7) to obtain the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of height less than h. We can construct a normal form using of the latter sword using Proposition 1.

Finally, consider the situation where [[rho].sub.1] falls in case 1). Assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [l.sub.1],[l.sub.2] [member of] Z and some non-empty [x'.sub.1]. If h([x.sub.0]) = h([x.sub.1]), then Lemma 4 implies [x.sub.0] = [x.sub.1], and the sword [x'.sub.0] has some [omega]-power of [x.sub.0] as a suffix. This would mean that the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not normal, a contradiction. If h([x.sub.0]) > h([x.sub.1]), then [x.sub.0] has a prefix of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] while [x'.sub.0] has a suffix of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and this again contradicts the assumption that [rho] is normal. Thus, we conclude that h([x.sub.0]) < h([x.sub.1]).

We proceed in the same way by reducing the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and letting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The only situation where we cannot immediately normalize the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is that where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [k.sub.1], [k.sub.2] [member of] Z and some non-empty [x'.sub.2]. In this situation, as the argument from the preceding paragraph shows, we must have h([x.sub.1]) < h([x.sub.2]). We then repeat the procedure, if necessary, until it eventually stops at some sword [[rho].sub.s] such that the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be reduced to a normal sword of the form [[beta].sup.[omega]+t] with h([beta]) < h. (Since the height of the overlaps [x.sub.0], [x.sub.1], [x.sub.2],... increases on each step, the number of steps is upper bounded by h.) Then the original [omega]-power [[rho].sup.[omega]+q] is reduced to the sword [[alpha].sub.1][[beta].sup.[omega]+t][[alpha].sub.2], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Now we are in a position to prove Proposition 1. Recall that is claims the existence of an algorithm that, given a sword [sigma] of height h, returns a normal form of [sigma].

Proof of Proposition 1: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a height representation of [sigma]. By the induction hypothesis, we assume that all the swords [[rho].sub.1],..., [[rho].sub.n] and [[pi].sub.0], [[pi].sub.1],..., [[pi].sub.n] are normal.

By Lemma 6, each sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be effectively reduced to a sword of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is normal of height h while the swords [[alpha].sub.i1], [[alpha].sub.i2] have height at most h - 1 and again may be assumed to be normal by the induction hypothesis. Then [sigma] reduces to the following product of normal factors:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The algorithm of Lemma 5 allows us to construct a normal form for the product of two normal swords. Clearly, applying this algorithm several times, we can construct a normal form for the product of any finite number of normal swords, and hence, a normal form for [sigma]. []

3.4 Longest common prefix

Here we prove Proposition 2. Recall that it claims the existence of an algorithm that, given two normal swords [sigma] and [delta], say, both of height at most h, returns their longest common prefix, which we denote by LCP([sigma], [delta]).

Proof of Proposition 2: We fix a height representation of the sword [sigma] with the minimum number of factors of height h and an analogous height representation of the sword [delta]. We are going to induct on the total number t of factors of height h in these two representations. If t = 0, then h([sigma]), h([delta]) < h and the hypothesis of external induction (on h) applies. Consider the situation where one of the swords [sigma] and [delta] has height less than h while the other has height h. For certainty, suppose that h([delta]) < h([sigma]) = h and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the chosen height representation of the sword [sigma]. Then LCP([sigma], [delta]) = LCP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) where k is any integer large enough to ensure that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since h([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) < h, we can construct LCP([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) using the external induction hypothesis. Therefore, we may assume that both [sigma] and [delta] have height h.

First consider a special case where [sigma] = [pi][[rho].sup.[omega]+q] and [delta] = [alpha][[beta].sup.[omega]+r] for some q, r [member of] Z, some swords [rho], [beta] of height h - 1 and some swords [pi], [alpha] of height at most h - 1.By symmetry, we may assume that |[alpha]| [less than or equal to] |[pi]|.

We start with finding [[tau].sub.1] = LCP([alpha],[pi]) using the external induction hypothesis. If |[[tau].sub.1]| < |[alpha]|, then clearly LCP([sigma], [delta]) =[[tau].sub.1]. Otherwise, [[tau].sub.1] = [alpha] and [pi] = [[tau].sub.1][pi]' for some sword [pi]' of height less than h. Now we should find the longest common prefix [[tau].sub.2] of the swords [[beta].sup.[omega]+r] and [pi]'[[rho].sup.[omega]+q]. First, we verify whether [[tau].sub.2] can be "long", that is, whether its length can exceed max{|[[beta].sup.2]|, |[pi]'[[rho].sup.2]|}. Since [[tau].sub.2] is a prefix of [[beta].sup.[omega]+r], we conclude that [pi]' = [[beta].sup.k][[beta].sub.1] for some integer k [greater than or equal to] 0 and some prefix [[beta].sub.1] of [beta]. Let [[beta].sub.2] be such that [beta] = [[beta].sub.1][[beta].sub.2]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and Lemma 4 implies that [rho] = [[beta].sub.2][[beta].sub.1], see Fig. 5. Hence, [pi]'[rho] = [[beta].sup.k][[beta].sub.1][[beta].sub.2][[beta].sub.1] = [beta][[beta].sup.k][[beta].sub.1] = [beta][pi]'. Given the swords [pi]', [rho], [beta], all of height less than h, we can verify whether the equality [pi]'[rho] = [beta][pi]' holds in view of Corollary 1. If the equality holds true, then clearly [pi]'[[rho].sup.[omega]] = [[beta].sup.[omega]][pi]' whence [tau]2 is the shortest of the swords [pi]'[[rho].sup.[omega]+q] and [[beta].sup.[omega]+r]. If the equality fails, we conclude that |[[tau].sub.2]| [less than or equal to] max{|[[beta].sup.2]|, |[pi]'[[rho].sup.2]|} and by the external induction assumption we can find [[tau].sub.2] as LCP([[beta].sup.l],[pi]'[[rho].sup.l]) where l is large enough to ensure that min{|[[beta].sup.l]|, |[pi]'[[rho].sup.l]|} > max(|[[beta].sup.2]|, |[pi]'[[rho].sup.2]|). Finally, we obtain LCP([sigma], [delta]) = [[tau].sub.1][[tau].sub.2].

[FIGURE 5 OMITTED]

Now consider the general case. Isolating the leftmost factors of height h in the height representations of the swords [sigma] and [delta] chosen at the beginning of the proof, we can represent these swords as follows:

[sigma] = [pi][[rho].sup.[omega]+q][sigma]', [delta] = [alpha][[beta].sup.[omega]+r][delta]',

where q,r [member of] Z, h([rho]) = h([beta]) = h - 1, h([alpha]), h([pi]) [less than or equal to] h - 1. Using the algorithm for the special case that we described above, we can construct [[gamma].sub.1] = LCP([pi][[rho].sup.[omega]+q], [alpha][[beta].sup.[omega]+r]). If h([[gamma].sub.1]) < h, then clearly LCP([sigma], [delta]) = [[gamma].sub.1]. Otherwise, the construction guarantees that [[gamma].sub.1] is the shortest of the swords [pi][[rho].sup.[omega]+q] and [alpha][[beta].sup.[omega]+r]. For certainty, suppose that [[gamma].sub.1] = [pi][[rho].sup.[omega]+q] and [alpha][[beta].sup.[omega]+r] = [[gamma].sub.1][delta]". Since the total number of factors of height h in some height representations of the swords [sigma]' and [delta]"[delta]' is smaller than t, we can apply the internal induction assumption to find [[gamma].sub.2] = LCP([sigma]', [delta]"[delta]'). Then LCP([sigma], [delta]) = [[gamma].sub.1][[gamma].sub.2]. []

In order to close the cycle of simultaneous induction, it remains to prove the following result:

Lemma 7 There exists an algorithm that, given a normal sword [sigma] of height h, decides whether or not there exists a fully normal sword x such that either [sigma] is an [omega]-power of x or there is an integer m [greater than or equal to] 2 such that [sigma] = [x.sup.m]. If the answer is positive, the algorithm finds x in the first case and all possible pairs (x, m) in the second case.

Proof: If [sigma] = [x.sup.[omega]+q] for some sword x and integer q, then |[sigma]| = ([omega] + q)|x| whence the number -q must be a root of the polynomial |[sigma]|. Thus, we can find all integer roots q1,... ,[q.sub.n] of |[sigma]| and for each i = 1,..., n, apply Lemma 1 to verify if [sigma] has a prefix [x.sub.i] of length |[sigma]|/([omega] + [q.sub.i]). If this is the case, it remains to verify whether [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and this can be done in view of Corollary 1.

Similarly, [sigma] = [x.sup.m] for some sword x and integer m [greater than or equal to] 2, then the number m divides all coefficients of the polynomial |[sigma]|. Thus, we can find all common divisors [m.sub.1],..., [m.sub.k] of the coefficients of |[sigma]| such that [m.sub.1],... , [m.sub.k] [greater than or equal to] 2. Then for each j = 1,..., k, we apply Lemma 1 to check if [sigma] has a prefix [x.sub.j] of length |[sigma]|/[m.sub.j], and if this is the case, we use Corollary 1 to verify whether [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

4 Proof of the theorem

4.1 Normal swords and epigroup identities

Recall that we consider epigroups as unary semigroups under the unary operation of pseudoinversion x |[right arrow] [bar.x]. It is known Shevrin (2005) that the following identities hold in the class E of all epigroups:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (9)

[[bar.x].sup.2] x [approximately equal to], [bar.x], (10)

[x.sup.2] [bar.x] [approximately equal to], [??], (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each prime p. (13)

We will often use also the identity [bar.x]x [approximately equal to] x[bar.x] that can be easily deduced from (9)-(13). Indeed,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Every unary semigroup term becomes a Z-unary word if one replaces every expression of the form [bar.x] by [x.sup.[omega]-1]. Conversely, every Z-unary word will be treated as an epigroup term in which expressions of the form [x.sup.[omega]+q], q [member of] Z, are interpreted as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proposition 3 If Z-unary words [sigma], [sigma]' are S-related, then the identity [sigma] [approximately equal to], [sigma]' holds in E.

Proof: It suffices to verify that, for every integer q, each epigroup satisfies the identities

x[x.sup.[omega]+q] [approximately equal to] [x.sup.[omega]+q+1] (14)

[x.sup.[omega]+q]x [approximately equal to] [x.sup.[omega]+q+1] (15)

[(xy).sup.[omega]+q]x [approximately equal to] x[(yx).sup.[omega]+q ](16)

that correspond to the pairs (2)-(4) generating the relation S as a fully invariant congruence.

First, suppose that q [greater than or equal to] 0. Then [x.sup.[omega]+q] = [bar.x][x.sup.q+1]. Note that, since [bar.x]x [approximately equal to] x[bar.x], we have [bar.x][x.sup.q+1] [approximately equal to] [x.sup.q+1][bar.x]. Therefore, the identities (14) and (15) clearly hold in E since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Consider the identity (16). We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now suppose that q < 0. In this case [x.sup.[omega]+q] = [[bar.x].sup.(-q)]. If q = -1, then the identity (14) becomes x[x.sup.[omega]-1] [approximately equal to] [x.sup.[omega]], and it clearly holds in E because x[x.sup.[omega]-1] = x[bar.x] while [x.sup.[omega]] = [bar.x]x. For q < - 1, we use (10) to obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The identity (15) is treated in the same way. Finally, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

thus establishing (16). []

Proposition 3 allows us to treat expressions of the form [sigma] [approximately equal to] [sigma]', with [sigma], [sigma]' being swords, as epigroup identities.

Proposition 4 Let [[sigma].sub.1] and [[sigma].sub.2] be two swords and let [[alpha].sub.1] and respectively [[alpha].sub.2] be their normal forms. Then the identity [[sigma].sub.1] [approximately equal to] [[sigma].sub.2] holds in E if and only if so does the identity [[alpha].sub.1] [approximately equal to] [[alpha].sub.2].

Proof: It is enough to show that if [alpha] is a normal form of a sword [sigma], then the identity [sigma] [approximately equal to] [alpha] holds in E. For this, it clearly suffices to prove that E satisfies the identities

[x.sup.[omega]+r ][x.sup.[omega]+q] [approximately equal to] [x.sup.[omega]+r+q] (17)

[([x.sup.n]).sup.[omega]+q] [approximately equal to] [x.sup.[omega]+nq], (18)

[([x.sup.[omega]+r]).sup.[omega]+q][approximately equal to] [x.sup.[omega]+rq ](19)

for all q, r [member of] Z and all n [greater than or equal to] 2 as these identities correspond to the reduction rules (5)-(7) used in the normalization procedure.

The proof of (17) splits in 4 cases depending on the signs of q and r. If q, r [greater than or equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If q, r < 0, the proof is straightforward since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Assume that r [greater than or equal to] 0 and q < 0. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, by the definition, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, we conclude that [x.sup.[omega]+r][x.sup.[omega]+q] [approximately equal to] [x.sup.[omega]+r+q]. The case where r < 0 and q [greater than or equal to] 0 is completely analogous.

Before we proceed with proving (18), we notice that the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds in E for every positive integer n. For this, we induct on n. The claim is trivial for n = 1. If n > 1, represent n as n = kp, with p being prime. Then we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the induction assumption whence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, for each q [greater than or equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For q < 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to verify (19), we first show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Indeed, substituting [bar.x] for x in (11), we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We use this to deduce yet another auxiliary identity, namely, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every integer r [member of] Z. If r > 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Here we have repeatedly employed (17) in the final step. If r = 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If r < 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now we are ready to deduce the identity (19). If q [greater than or equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and if q < 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the final steps in each of the two deductions follow from (17). []

4.2 Connections to Burnside varieties

For any pair (m, k) of positive integers, the semigroup variety [B.sub.m,k] defined by the identity [x.sup.m] [approximately equal to] [x.sup.m+k] is called a Burnside variety. Let A be a finite set and denote by B (A, m, k) the free A-generated semigroup in the variety [B.sub.m,k]. We recall some results due to Victor Guba Guba (1993a,b).

Theorem 2 (Guba (1993b), Theorem A) For m [greater than or equal to] 3, k [greater than or equal to] 1, the word problem for the semigroup B(A, m, k) is decidable.

Theorem 3 For m [greater than or equal to] 3, k [greater than or equal to] 1, every element of the semigroup B(A, m, k) has a finite number of factors.

The next statement easily follows from Theorem 3. We supply a proof for the sake of completeness.

Proposition 5 For m [greater than or equal to] 3, k [greater than or equal to] 1, the Burnside variety [B.sub.m,k] is generated by its finite members.

Proof: Take any two different elements a, b [member of] B (A, m, k) and let [F.sub.ab] the set of all factors of their product ab. By Theorem 3, [F.sub.ab] is finite, and it is easy to see that the set I (ab) = B (A, m, k) \ [F.sub.ab] forms an ideal of B (A, m, k). Thus, the Rees quotient B (A, m, k)/I(ab) is finite and the natural homomorphism B (A, m, k) [right arrow] B (A, m, k)/I(ab) separates a and b since a, b [??] I (ab). Therefore, the semigroup B (A, m, k) is residually finite for any finite set A. Since each variety is generated by the collection of its finitely generated free objects, the variety [B.sub.m,k] is generated by its finite members. []

In the sequel, it will be convenient to consider only the varieties [B.sub.m,k] with k > m. Observe that every such variety satisfies the identity [x.sup.k] [approximately equal to] [x.sup.2k]. Indeed,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Semigroups in the Burnside varieties are periodic, and hence, we may (and will) treat them as epigroups. It is easy to see that in every epigroup from [B.sub.m,k] with k > m one has [bar.x] = [x.sup.k-1] and [x.sup.[omega]] = [bar.x]x = [x.sup.k].

Let [alpha] be a Z-unary word. We define the depth of [alpha] as follows:

d([alpha]) := max{0, -q | the expression [omega] + q occurs in [alpha]}.

For instance, d ([([x.sup.[omega]-4]y[x.sup.[omega]+30]).sup.[omega]-1]x[y.sup.[omega]]) = 4. Given an integer k > d([alpha]), we denote by [[alpha].sup.(k)] the expression obtained from [alpha] by substituting k for each occurrence of [omega] in [alpha]. The inequality k > d([alpha]) ensures that after the substitution, all expressions [omega] + q involved in [alpha] become positive integers, and hence, [[alpha].sup.(k)] is in fact a well-formed ordinary word. Now take any l > d([alpha]), any k > l and let m = k - l. Then it is easy to see that the identity [alpha] [approximately equal to] [[alpha].sup.(k)] holds true in the variety [B.sub.m,k].

We want to extend "ordinarization" transforms of the form [alpha] [??] [[alpha].sup.(k)] to swords. There is a subtlety here because the concept of depth is well defined only for Z-unary words and not for swords: if two Z-unary words [alpha] and [alpha]' are obtained from each other by "unwinding" or "winding up", they represent the same sword, but the equality d([alpha]) = d([alpha]') need not be true. Therefore, given a sword [sigma], we should first fix a Z-unary word [alpha] representing [sigma] and choose an integer k strictly larger than d([alpha]); we then denote by [[sigma].sup.(k)] the word [[alpha].sup.(k)]. Observe that the conclusion that the identity [sigma] [approximately equal to] [[sigma].sup.(k)] holds in the variety [B.sub.m, k] remains valid for every choice of a Z-unary word representing the sword [sigma] provided that k is strictly larger than m and t = k - m is is strictly larger than the depth of the chosen Z-unary word.

We need also yet another auxiliary construction [sigma] [??] [sigma] that associates ordinary words to swords. Again, it is first defined for Z-unary words and then we extend it to swords by utilizing the same approach as above, that is, by fixing a Z-unary word representing a given sword. If [alpha] is a Z-unary word, we define [alpha] using induction on height. If h([alpha]) = 0, i.e., if [alpha] is an ordinary word, then [alpha] := [alpha]. If h([alpha]) > 0, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the height representation of [alpha]. Then for each i = 1,..., n, we define [q'.sub.i] = 2 if [q.sub.i] [less than or equal to] 2 and [q'.sub.i] = [q.sub.i] otherwise, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For instance, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [sigma] = [([x.sup.2]y[x.sup.30]).sup.2]y[x.sup.2].

In the following statements and their proofs, whenever both constructions [[sigma].sup.(k)] and [sigma] are used, we assume that they are produced from the same Z-unary word representing the sword [sigma].

Lemma 8 Let [[sigma].sub.1], [[sigma].sub.2] be two normal swords. Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every choice of Z-unary words representing [[sigma].sub.1] and [[sigma].sub.2], every l > max{d([[sigma].sub.1]), d([[sigma].sub.2])} and every k such that k - l - 2 > max{[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}. Then [[sigma].sub.1] = [[sigma].sub.2].

Proof: Suppose that [[sigma].sub.1] [not equal to] [[sigma].sub.2]. Let [tau] be the longest common prefix of [[sigma].sub.1] and [[sigma].sub.2] (it exists by Proposition 2). We write [[sigma].sub.1] and [[sigma].sub.2] as [[sigma].sub.1] = [tau][[rho].sub.1] and [[sigma].sub.2] = [tau][[rho].sub.2] for some swords [[rho].sub.1] and [[rho].sub.2] such that either one of them is empty while the other is not or they both are non-empty and start with different letters. Consider some Z-unary words [alpha], [[beta].sub.1], [[beta].sub.2] representing the swords [tau], [[rho].sub.1], [[rho].sub.2] respectively. Then, clearly, the Z-unary words [alpha][[beta].sub.1] and [alpha][[beta].sub.2] represent the swords [[sigma].sub.1] and respectively [[sigma].sub.2]. If the parameters t and k are calculated from these representations, then we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, the swords [[rho].sub.1] and [[rho].sub.2] that differ at their start should become equal when each [omega] in them is substituted with k. This is obviously not possible one of the swords is empty while the other is not since no ordinarization transform sends a non-empty sword to the empty word. Nor is it possible if [[rho].sub.1] and [rho]2 are non-empty and start with different letters because the starting letters of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] remain the same as the ones of [[rho].sub.1] and respectively [[rho].sub.2]. Thus, we arrive at a contradiction. []

Recall that an ordinary word u is said to be periodic if u = [v.sup.n] for some word v and some n [greater than or equal to] 2.

Lemma 9 Let [sigma] be a normal sword. It is periodic if and only if the word [[sigma].sup.(k]) is periodic for every choice of a Z-unary word representing [sigma], every i > d([sigma]) and every k such that k - l - 2 > |[sigma]|.

Proof: If [sigma] is a power then so is [sigma](k), and if [sigma] is an [omega]-power, say, [sigma] = [[tau].sup.[omega]+q], then [[sigma].sup.(k)] = [([[tau].sup.(k)]).sup.k+q], and conditions imposed on k guarantee that k + q [greater than or equal to] 2. Conversely, suppose that an ordinarization of the sword [sigma] is equal to [v.sup.n] for some word v and some n [greater than or equal to] 2. Then a Z-unary word representing [sigma] should decompose as [[alpha].sub.1]... [[alpha].sub.n], where the ordinarization sends each factor [[alpha].sub.i], i = 1,..., n, to the word v. If the parameters t and k are calculated from this representation of the sword [sigma] and [[tau].sub.i] is the normal sword represented by [[alpha].sub.i],i = 1,..., n, we have [sigma] = [[tau].sub.1]... [[tau].sub.n] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each i = 1,..., n. Since |[[tau].sub.i]| [less than or equal to] |[sigma]|, we can apply Lemma 8 to the swords [[tau].sub.i] and obtain that they are all equal. Therefore [sigma] is periodic. []

A central concept in Guba's papers Guba (1993a,b) is the notion of the reduced form of a word relative to the Burnside variety [B.sub.m, k]. We are not going to reproduce here the original definition of this notion because it is quite involved (it is given by simultaneous induction on five other notions) and because, as the reader will see, we can easily bypass the definition by working with a sufficient condition for a word to be in the reduced form (see Lemma 10 below). First we reproduce a result which is crucial for our considerations; it constitutes the main point of the proof of Theorem 4.1 in Guba (1993a).

Theorem 4 Let m [greater than or equal to] 3, k [greater than or equal to] 1, and let u and v be words. The identity u [approximately equal to] v holds in the variety [B.sub.m,k] if and only if u and v have the same reduced forms relative to [B.sub.m,k].

Now we again assume that k > m and, as above, let l = k - m. For short, words that are in the reduced form relative to [B.sub.m,k] will be called [B.sub.m,k]-reduced words. The following result that is a consequence of Lemma 2.2 in Guba (1993a) is sufficient for our purposes.

Lemma 10 Let k > m [greater than or equal to] 3 and i = k - m. A word is [B.sub.m,k]-reduced if it contains no factors of the form [v.sup.2k-l-2]

We use Lemma 10 to prove that, for a normal sword [sigma] and large enough k, the word [[sigma].sup.(k)] is [B.sub.m,k]-reduced. We start with considering swords of height 1.

Lemma 11 Let [sigma] be a normal sword of height 1 and i > d([sigma]), k - i - 2 > |[sigma]|. Then the word [[sigma].sup.(k)] is [B.sub.m,k]-reduced.

Proof: Since h([sigma]) = 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some ordinary words [u.sub.0], [u.sub.1],... [u.sub.n], [v.sub.1],..., [v.sub.n]. Suppose that for some word v, the word [[sigma].sup.(k)] has a factor of the form [v.sup.2k-l-2] First assume that v = [v.sub.i] for some i = 1,..., n. Since the sword [sigma] is normal, Lemma 4 implies that the sword [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not a factor of any [v.sub.i] -periodic sword. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a factor of the word [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider the word [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [q'.sub.i] = 2 if [q.sub.i] [less than or equal to] 2 and [q'.sub.i] = qi otherwise. Its length is not larger than |[sigma]|. But |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| > k - l - 2 > |[sigma]|. This implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cannot be a factor of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, the word [v.sup.2k-l-2] is a product of words of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [t.sub.1] is either a suffix of [u.sub.i] or equals to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is either a prefix of [u.sub.j+1] or equals to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let L = max{|[v.sub.i]|| [v.sub.i] is a factor of the word v}. Then [|v|.sup.2k-l-2] [less than or equal to]|[sigma]| + Lk. On the other hand, [|v|.sup.2k-l-2] [greater than or equal to] |v|k + k - l -2 > |v|k + |[sigma]|. This implies |v| < L, a contradiction. []

Now we consider the swords of larger height.

Lemma 12 Let [sigma] be a normal sword of height h > 1 then, for all integers k, p such that p > p([sigma]) and k - l - 2 > |[sigma]|, the word [[sigma].sup.(k)] is a [B.sub.m,k]-reducedform.

Proof: We are going to prove this lemma by induction on height of the sword [sigma] using Lemma 11 as the basis of induction.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a height representation of the sword [sigma]. Consider the sword

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

of height 1. Note that [[sigma].sup.(k)] = [[sigma].sup.(k)].

By the induction hypothesis we have that all the words [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are [B.sub.m,k]-reduced forms. Let us prove now that [sigma] is a normal sword. Indeed, the words [[rho].sub.i] are not periodic by Lemma 9. Next, suppose that, for some index [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [[alpha].sub.1], [[alpha].sub.2],[[beta].sub.1], [[beta].sub.2] be swords such that [[alpha].sub.1][[alpha].sub.2] = [[rho].sub.i], [[beta].sub.1][[beta].sub.2] = [[rho].sub.i+1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Again by Lemma 8 the following equalities hold [[alpha].sub.1] = [beta]2 = [[pi].sub.i], [[alpha].sub.2] = [[beta].sub.1]. Thus,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subsword of the normal sword [sigma]. This implies that the sword [sigma] is normal.

We proceed assuming that the word [sigma] is not a [B.sub.m,k]-reduced form and, for some word T, it contains [T.sup.2k-l-2] as a factor Similarly to the proof of Lemma 11 suppose firstly that, for some index [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Again the word [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can not be some factor of some T-periodic sword by Lemma 4. Thus, |[tau]| > | [T.sup.2k-l-2]| and the length of [[tau].sup.(k)] does not exceed |[sigma]| + |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| |k. On the other hand, |[T.sup.2k-l-2]| = |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]|(2k - l - 2) > |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| k + |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| ||[sigma]|, a contradiction.

Suppose now that T has the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [t.sub.1] is a suffix of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a prefix of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let L be the maximum of |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| | where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a factor of T. Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But [|T|.sup.2k-l-2] = |T|k + |T|(k - i - 2) > |T|(k + |[sigma]|) > L(k + |[sigma]|).

Hence, the word [[sigma].sup.(k)] that equals to [[sigma].sup.(k)] is a [B.sub.m,k]-reduced form. []

These lemmas lead us to the important

Proposition 6 Let [[sigma].sub.1], [[sigma].sub.2] be two normal swords then the equality [[sigma].sub.1] [approximately equal to] [sigma]2 holds in E ([E.sub.fin]) if and only if [[sigma].sub.1] and [[sigma].sub.2] are equal.

Proof: Remind that every Burnside semigroup is an epigroup. Also, in view of Proposition 5 the free Burnside semigroup satisfies any identity that holds in [E.sub.fin]. Thus, the identities [[sigma].sub.1] [approximately equal to] [[sigma].sub.2] and, therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds in the variety [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for large enough k, l and m = k - t. By Lemmas 11 and 12 the words [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are [B.sub.m, k]-reduced forms. Then by Theorem 4 the words [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are equal. Hence, by Lemma 8 the swords [[sigma].sub.1] and [[sigma].sub.2] coincide. []

Proof of Theorem 1: Let [[sigma].sub.1] [approximately equal to] [[sigma].sub.2] be any identity that holds in [E.sub.fin] or E. By Proposition 1 there is an algorithm that constructs normal forms [[alpha].sub.1], [[alpha].sub.2] of the swords [[sigma].sub.1], [[sigma].sub.2] respectively and the identity [[alpha].sub.1] [approximately equal to] [[alpha].sub.2], by Proposition 4, also holds in [E.sub.fin] or E. By Proposition 6 this identity is equivalent to the equality of the swords [[alpha].sub.1] and [[alpha].sub.2] which we can check using algorithm from Proposition 2.

The following proof was given by M. Volkov in a verbal discussion. Let us prove that the identity basis of E is infinite. For a prime number p, consider a non-trivial group G satisfying the identity [x.sup.p] [approximately equal to] 1. Let H be the semigroup G with adjoined 0. Define a unary operation on H by the following rule: for all x [not equal to] 1 we set [bar.x] = 0, and [bar.1] = 1. It is clear that the unary semigroup H satisfies the first five identities.

Let q be a prime number distinct from p and let x [member of] H. Then [x.sup.q] [not equal to] 1 if and only if x [not equal to] 1. Therefore, for x [not equal to] 1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds in H. Meanwhile, taking x [member of] G distinct from 1 we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] fails in H. []

Acknowledgements

The author wants to thank M. Volkov who drew her attention to this problem and helped to improve the paper, the anonymous reviewer for many valuable remarks and suggestions, A. Popovich for help in finishing this work and opportunity to discuss the results and L. Shevrin for useful comments.

The author acknowledges support from the Presidential Programme "Leading Scientific Schools of the Russian Federation", project no. 5161.2014.1, the Russian Foundation for Basic Research, project no. 14-01-00524, the Ministry of Education and Science of the Russian Federation, project no. 1.1999.2014/K, and the Competitiveness Program of Ural Federal University.

References

J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, 1995.

J. Almeida and B. Steinberg. On the decidability of iterated semidirect products and applications to complexity. Proceedings of the London Mathematical Society, 80:55-74, 2000.

J. C. Costa. Canonical forms for free [kappa]-semigroups. Technical report, Universidade do Minho, 2013. URL http://arxiv.org/abs/1309.1450.

J. C. Costa. Canonical forms for free [kappa]-semigroups. Discrete Math. Theor. Comput. Sci, 26:159-178, 2014.

V. Guba. The word problem for the relatively free semigroup satisfying [t.sup.m] = [t.sup.m+n] with m [greater than or equal to] 4 or m = 3, n = 1. International Journal of Algebra and Computation, 3:125-140, 1993a.

V. Guba. The word problem for the relatively free semigroup satisfying [t.sup.m] = [t.sup.m+n] with m [greater than or equal to] 3. International Journal of Algebra and Computation, 3:335-347, 1993b.

J. McCammond. Normal forms for free aperiodic semigroups. International Journal of Algebra and Computation, 11:581-625, 2001.

J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14:1-10, 1982.

L. N. Shevrin. On the theory of epigroups. I. Russian Acad. Sci. Sb. Math., 82:485-512, 1994a.

L. N. Shevrin. On the theory of epigroups. II. Russian Acad. Sci. Sb. Math., 83:133-154, 1994b.

L. N. Shevrin. Epigroups. In V. B. Kudryavtsev and I. V. Rosenberg, editors, Structural theory of automata, semigroups, and universal algebra, Proc. NATO Advance Study Institute Workshop at the CRM, pages 331-380. Springer, 2005.

I. Y. Zhil'tsov. On [omega]-identities of finite semigroups. In C. L. Nehaniv and M. Ito, editors, Algebraic Engineering, Proc. Kyoto Workshop on Computer Systems and Formal Languages and First International Conference on Semigroups and Algebraic Engineering, pages 427-436. World Scientific, 1999.

I. Y. Zhil'tsov. On identities of epigroups. Doklady Mathematics, 375:10-13, 2000.

Inna Mikhailova (*)

Ural Federal University, Ekaterinburg, Russia

received 11th Sep. 2013, revised 16th Nov. 2014, 18th Dec. 2015, accepted 10th May 2016.

(*) Email: inna.mikhaylova@gmail.com

(i) In order to prevent any chance of confusion, we mention here that the class E does not form a variety of unary semigroups; of course, this is not an obstacle for considering the equational theory of E.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mikhailova, Inna
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:15510
Previous Article:Permutations of context-free, ET0L and indexed languages.
Next Article:The irregularity of two types of trees.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters