Printer Friendly

Factoriality and the Pin-Reutenauer procedure.

We consider implicit signatures over finite semigroups determined by sets of pseudonatural numbers. We prove that, under relatively simple hypotheses on a pseudovariety V of semigroups, the finitely generated free algebra for the largest such signature is closed under taking factors within the free pro-V semigroup on the same set of generators. Furthermore, we show that the natural analogue of the Pin-Reutenauer descriptive procedure for the closure of a rational language in the free group with respect to the profinite topology holds for the pseudovariety of all finite semigroups. As an application, we establish that a pseudovariety enjoys this property if and only if it is full.

Keywords: pseudovariety, profinite semigroup, profinite topology, topological closure, unary implicit signature, pure implicit signature, rational language, aperiodic semigroup, Burnside pseudovariety, factorial pseudovariety, full pseudovariety, Pin-Reutenauer procedure

1 Introduction

Context and motivations. This paper deals with the computation of the closure of a given rational language within a relatively free algebra, with respect to a suitable implicit signature and a profinite topology. A motivation for this line of research is the separation problem, which, given two rational languages K and L, asks whether there is a rational language from a fixed class C containing K and disjoint from L. The separation problem has several motivations. First, the membership problem for C reduces to the separation problem for C, since a language belongs to the class C if and only if it is separable from its complement by a language from C.

Furthermore, solving this problem gives more information about the class under investigation, and is more robust when applying transformations to the class. For instance, is was proved by Steinberg (2001) and Place and Zeitoun (2015) that the classical operator V [??] V * D on pseudovarieties preserves decidability of the separation problem, while it has been shown by Auinger (2010) that it does not preserve decidability of the membership problem (on the other hand, the status with respect to separation is unknown for other operators that do not preserve the decidability of membership, such as the power, as shown by Auinger and Steinberg (2003)).

Finally, deciding separation for some class can be used to decide membership for more involved classes: this is for instance a generic result in the quantifier alternation hierarchy, established by Place and Zeitoun (2014a), that deciding separation at level [[summation].sub.n] in this hierarchy entails a decision procedure for membership at level [[summation].sub.n+1].

Almeida (1999) has related the separation problem with a purely topological question, which is the main topic of this paper: the separation problem has a negative answer on an instance K, L of rational languages if and only if the closures of K and L in a suitable relatively free profinite semigroup, which depends on the class of separator languages we started from, have a nonempty intersection. Determining whether such closures intersect can be in turn reformulated in terms of computation of pointlike two-element sets in a given semigroup.

Deciding whether closures of rational languages intersect is often nontrivial, in particular because the profinite semigroup in question is uncountable in general. Yet, several classes of languages enjoy a property called [reducibilit.sup.(i)] that states that the closures of two rational languages intersect in the suitable relatively free profinite semigroup if and only if their traces in a more manageable universe also intersect. This more manageable universe may in particular be countable, and is therefore amenable to algorithmic treatment. In summary, reducibility is a property of the class of separators under investigation (or of the class of semigroups recognizing these separators), which reduces the search of a witness in the intersection into a simpler universe.

The most important example from the historical point of view is the class of languages recognized by finite groups. In this case, the relatively free algebra is the free group over some set X of generators, which is indisputably much better understood than the free profinite group over X. In particular, it is countable. Since it is known that the closures in the free profinite group of two rational languages intersect if and only if their traces in the free group also intersect (that is, the class of finite groups enjoys the reducibility property), this justifies the quest for an algorithm computing the closure in the free group of a rational language. Such an algorithm is known as the Pin-Reutenauer procedure, which we describe below, and has been developed along a successful line of research, see the work of Pin and Reutenauer (1991); Pin (1991); Ash (1991); Henckell et al. (1991); Ribes and Zalesskii (1993); Herwig and Lascar (2000); Auinger (2004); Auinger and Steinberg (2005). As a consequence, the separation problem by group languages is decidable.

This framework can be generalized to classes consiting of other types of semigroups than just groups. Denote by [kappa] the signature consisting of the binary multiplication and the unary ([omega] - 1)-power, with their usual interpretation in profinite semigroups. Note that the set of all [kappa]-terms over X is isomorphic to the free group over X : the mapping sending each generator to itself and [x.sup.[omega]-1] to [x.sup.-1], the inverse of x in the free group, can be extended to a group isomorphism. More generally, given a pseudovariety V of finite semigroups, consider the semigroup [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which can be seen as the set of all interpretations over V of [kappa]-terms over X. This subalgebra of the pro-V semigroup over X is countable and thus, as said above, amenable to algorithmic treatment. One central problem in this context is the [kappa]-word problem: given two [kappa]-terms over X, decide whether they represent the same element in the relatively free profinite semigroup in the pseudovariety under consideration. This problem has already been investigated for several classical pseudovarieties besides that of finite groups, for instance by Almeida (1991, 1995) for the pseudovariety J of all finite [??]-trivial semigroups, by Almeida and Zeitoun (2004, 2007) for the pseudovariety R of all finite R-trivial semigroups, by Costa (2001) for the pseudovariety LSI of all finite semigroups whose local monoids are semilattices and by Moura (2011) for the pseudovariety DA of all finite semigroups whose regular [??]-classes are aperiodic semigroups. Moreover, reducibility has been shown to hold for several pseudovarieties, in particular by Almeida (2002) for J, by Almeida et al. (2005) for R, by Costa and Teixeira (2004) for LSI and, as already mentioned, by Ash (1991); Almeida and Steinberg (2000a) for the pseudovariety G of all finite groups. A further example is the pseudovariety A of aperiodic languages which, in a forthcoming paper, will be derived from the work of Henckell (1988), recently revisited by Place and Zeitoun (2014b, 2016), from which one can derive reducibility of this class. In other words, for these classes of languages, the separation problem reduces to testing that the intersection of the closures of two given rational languages in the suitable countable relatively free algebra is empty. This motivates designing algorithms to compute closures of rational languages in these relatively free algebras. This is one of the main contributions of this paper.

The Pin-Reutenauer procedure. In the core of the paper, we investigate how the profinite closure of rational languages in free unary algebras interacts with concatenation and iteration. The natural guide for this work is provided by a procedure proposed by Pin and Reutenauer (1991) for the case of the free group. This procedure gives a way to compute a representation of the closure of a rational language inductively on the structure of the rational expression. Of course, the closure of a union is the union of the closures. The other two rules of the Pin-Reutenauer procedure deal with concatenation and iteration. For instance, when computing in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the smallest subalgebra of the pro-V semigroup closed under multiplication and ([omega] - 1)-power, establishing the Pin-Reutenauer procedure amounts to showing the following equalities:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [bar.L] is the topological closure of L in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [<L>.sub.[kappa]] is the subalgebra of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] generated by L. Notice that these equalities yield a recursive procedure to compute a finite algebraic representation of [??] when L is rational. Such a finite representation may not immediately yield algorithms to decide membership in [bar.L] for a given rational language L, but it reduces the problem of computing topological closures [??] to the problem of computing algebraic closures [<L>[kappa]]. Since the signature [kappa] is finite, this representation also provides a recursive enumeration of elements of [bar.L]. Additionally, assume that the following two properties hold:

(1) the word problem for [kappa]-terms over V is decidable,

(2) the pseudovariety V is [kappa]-reducible.

Then one can decide the separation problem of two rational languages K, L by a V-recognizable language. Indeed, Almeida (1999) has shown that this problem is equivalent to checking whether the closures of K and L in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersect, which by reducibility is equivalent to checking whether [??] [intersection] [??] [not equal to] [??]. In turn, this may be tested by running two semi-algorithms in parallel:

(1) one that enumerates elements of [bar.K] and [bar.L] and checks, using the solution over V of the word problem for [kappa]-terms, whether there is some common element;

(2) another one that enumerates all potential V-recognizable separators.

Thus, the Pin-Reutenauer procedure is one of the ingredients to understand why a given class has decidable separation problem.

Contributions. It has been established recently by Almeida et al. (2014) that The Pin-Reutenauer procedure holds for a number of pseudovarieties. However, the results of this paper rely on independent, technically nontrivial results for the pseudovariety A of aperiodic semigroups: first, it was proved that the Pin-Reutenauer procedure is valid for A using the solution of the word problem for the free aperiodic [kappa]-algebra givenby McCammond (2001); Huschenbett and Kufleitner (2014); Almeida et al. (2015). Then, a transfer result was established to show that it is also valid for subpseudovarieties of A.

In this paper, we revisit the Pin-Reutenauer procedure, obtaining general results with simpler arguments. We consider unary signatures, made of multiplication and operations of arity 1. Our main result, Theorem 3.1, establishes that the Pin-Reutenauer procedure holds for the pseudovariety S of all finite semigroups, for unary signatures satisfying an additional technical condition, which is met for [kappa]. The fact that rational languages are involved is crucial, since, as observed by Almeida et al. (2014, p. 10), the equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] fails for some languages K, L [??] [X.sup.+], where closures are taken with respect to S and the signature [kappa].

This result is obtained by first investigating a property named factoriality. Factoriality of V with respect to, say, the signature [kappa] means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is closed under taking factors in [[??].sub.X]V. It was shown by Almeida et al. (2014) that if V is factorial, then the Pin-Reutenauer procedure holds with respect to concatenation, that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for arbitrary K, L (not just for rational ones). However, it was also noted that the pseudovariety S cannot be factorial for nontrivial countable signatures, such as [kappa]. In contrast, we show that any nontrivial pseudovariety of semigroups V closed under concatenation is factorial for the signature 1 consisting of multiplication and all unary operations. As an application, we obtain a new proof that the minimum ideal of the free pro-V semigroup on at least two generators contains no 1-word. This property is a weaker version of a result obtained by Almeida and Volkov (2006). Besides the independent interest of such results, the technical tool used to prove them, named factorization history, is also the key to establish that the Pin-Reutenauer is valid for S. We further characterize pseudovarieties in which the Pin-Reutenauer procedure holds in terms of an abstract property named fullness, introduced by Almeida and Steinberg (2000a). The main idea is that the validity of the Pin-Reutenauer procedure for a pseudovariety V is inherited by a subpseudovariety W, as established by Almeida et al. (2014), provided both V and W are full. Conversely, we prove that if the Pin-Reutenauer procedure works for V, then V is full. Since the pseudovariety of all finite semigroups is full, this yields that a pseudovariety enjoys the Pin-Reutenauer property if and only if it is full.

Finally, we show that a variation of the Pin-Reutenauer procedure, known to hold in the case of all groups, also holds for pseudovarieties of groups in which every finitely generated subgroup of the free [kappa]-algebra is closed.

Organization. The paper is organized as follows. In Section 2, we introduce the notion of history of a factorization and we show that any nontrivial pseudovariety closed under concatenation product is 1-factorial. In Section 3, we establish that the Pin-Reutenauer property holds for S and unary signatures satisfying an additional condition. In Section 4, we relate the Pin-Reutenauer property with fullness, in the general case and in the case of pseudovarieties of groups.

2 1-factoriality

We assume that the reader has some familiarity with profinite semigroups. For details, we refer the reader to the books of Almeida (1995); Rhodes and Steinberg (2009) and to the article of Almeida (2005). Here, we briefly introduce the required notation and key notions.

Preliminaries. Throughout the paper, we work with a finite alphabet X. For a pseudovariety V of semigroups, we denote by [[??].sub.X]V the free pro-V semigroup generated by X. Elements of [[??].sub.X]V are called X -ary implicit operations over V. See the paper of Almeida (1995) for details.

An implicit signature, as defined by Almeida and Steinberg (2000a), is a set of implicit operations of finite arity including the formal binary multiplication. A [sigma]-semigroup is an algebra in the signature [sigma] whose multiplication is associative. Thus, [sigma]-semigroups form a Birkhoff variety. We call an element of the free [sigma]-semigroup generated by X a [sigma]-term. For convenience, we allow the empty [sigma]-term.

Every pro-V semigroup has a natural structure of [sigma]-semigroup. We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the sub-[sigma]-semigroup of [[??].sub.X]V generated by X. A [sigma]-word over V is an element of [sigma]. We denote by [_]v the surjective homomorphism of [sigma]-semigroups that associates to a [sigma]-term t its interpretation [t]V in [sigma]. When t is a word and V is clear from the context, we write t instead of [t]V.

Unary implicit signatures. Let [??] be the profinite completion of (N, +), i.e., the free profinite monoid on one generator. We denote by [??] the implicit signature consisting of multiplication together with all implicit operations [_.sup.[alpha]] with [alpha] [member of] [??] N. An implicit signature is called unary if it is contained in [??] and it contains at least one unary implicit operation. For a unary implicit signature [sigma], an element [alpha] [member of] [??] such that the [alpha]-power operation [_.sup.[alpha]] belongs to a is said to be a [sigma]-exponent. Note that by definition of [??], every [sigma]-exponent is infinite. An important example of a unary implicit signature is the signature [kappa], for which [omega] - 1 is the only [kappa]-exponent.

The [sigma]-rank [rank.sub.[sigma]] (t) of a [sigma]-term t is the maximal nesting depth of elements of [sigma], disregarding multiplication, that occur in t. It is defined inductively by [rank.sub.[sigma]]([t.sub.1][t.sub.2]) = max([rank.sub.[sigma]]([t.sub.1]), [rank.sub.[sigma]]([t.sub.2])) and [rank.sub.[sigma]] ([pi]([t.sub.1],..., [t.sub.n])) = 1 + [max.sub.1,...,n]([rank.sub.[sigma]] ([t.sub.i])) incase [pi] is an operation from [sigma] which is not multiplication. For a [sigma]-term

[sigma] (2.1)

where the [t.sub.i]'s and the [s.sub.j]'s are [sigma]-terms such that [rank.sub.[sigma]]([t.sub.i]) [??] [rank.sub.[sigma]]([s.sub.j]) = [rank.sub.[sigma]](t) - 1 and each [[alpha].sb.j] is a [sigma]-exponent, we denote by [v.sub.[sigma]] (t) the number m of subterms [sigma] of t. When a is clear from the context, we may write rank(t), v(t) instead of [rank.sub.[sigma]] (t), [v.sub.[sigma]](t), respectively.

Complete unary implicit signatures. A unary implicit signature [sigma] is said to be complete if the set of [sigma]-exponents is stable under the mappings [alpha] [??] [alpha] - 1 and [alpha] [??] [alpha] +1. Note that [??] is complete, while [kappa] is not. The intersection of a nonempty set of complete unary signatures either consists of multiplication solely, or is again a complete unary signature. Therefore, the smallest complete unary signature containing a given unary signature [sigma] exists. It is called the completion of [sigma] and it is denoted by [??]. By definition, we have [sigma] [??] [??], and a signature [sigma] is complete if and only if [??] = [sigma]. Note that for every [??]-exponent [alpha] and every u [member of] [[bar.[OMEGA]].sub.X]S, the equalities [u.sup.[alpha]-1] = [u.sup.[alpha]][u.sup.[omega]-1] and [u.sup.[alpha]+1] = [u.sup.[alpha]]u hold. This proves the following useful fact.

Remark 1. Let a be a unary signature containing [kappa]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.1 Factorization sequences

For [alpha] [member of] [??], we choose a sequence ([[xi].sub.n][([alpha])).sub.n] of natural integers converging to [alpha]. One can assume that ([[xi].sub.n][([alpha])).sub.n] is constant if [alpha] is finite, or strictly increasing otherwise. Let t be a [??]-term. We denote by [[xi].sub.n] (t) the word obtained by replacing each subterm [v.sup.[alpha]] with [alpha] infinite by [v.sup.[xi]n ([alpha])], recursively. For instance, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The factorizations [[xi].sub.n](t) = x * y with x [member of] [X.sup.*] and y [member of] [X.sup.+] may be obtained recursively as follows:

* if rank(t) = 0, then [[xi].sub.n] (t) = t for all n and there are |t| such factorizations of [[xi].sub.n] (t);

* if rank(t) > 0 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where the [t.sub.i]'s and the [s.sub.j]'s are [sigma]-terms such that rank([t.sub.i]) [??] rank([s.sub.j]) = rank(t) - 1 (where the [t.sub.i]'s may be empty), then the factorizations of [[xi].sub.n] (t) are those of the following forms:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.2)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.3)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [kappa] + [??] + 1 = [[xi].sub.n]([[alpha].sub.j]).

The condition y [member of] [X.sup.+], forbidding y to be empty, is used recursively to ensure that each factorization of [[xi].sub.n](t) is either of type (2.2) or (2.3), but not of both types: one can verify that each factorization of [[xi].sub.n](t) is obtained by exactly one of the equations (2.2) and (2.3), where j,[t'.sub.j],[t".sub.j] (in case (2.2)), or j, k, l, [s'.sub.j], [s".sub.j] (in case (2.3)) are uniquely determined. In particular, the factorization

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

cannot be of type (2.2), since this would force [t".sub.p] to be empty, which is forbidden. This factorization is in fact of type (2.3) with j = p +1 and [kappa] = 0.

As an example, for t = [a.sup.[omega]][ba.sup.[omega]], the expression (2.1) is obtained for m = 2, where [t.sub.0] and [t.sub.2] are empty, while [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assuming [[xi].sub.n]([omega]) = n!, we obtain

--the factorization [a.sup.n!] * [ba.sup.n!] by (2.2), with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] empty and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

--the factorization [a.sup.n!]b * [a.sup.n!] by (2.3), j = 2, k = 0, [??] = n! - 1, [??] empty and [??] = a.

The history [h.sub.n] (t, x, y) of a factorization [[xi].sub.n] (t) = xy is defined recursively as follows:

--if rank(t) = 0, then [h.sub.n](t, x, y) = (x, y);

--if rank(t) > 0 and the factorization is of the form (2.2), then [h.sub.n] (t, x, y) is obtained by concatenating the pair (1, j) with [h.sub.n]([t.sub.j],[t'.sub.j],[t".sub.j]);

--if rank(t) > 0 and the factorization is of the form (2.3), then [h.sub.n] (t, x, y) is obtained by concatenating the 4-tuple (2, j, k, l) with [h.sub.n]([s.sub.j],[s'.sub.j],[s".sub.j].

The history [h.sub.n](t, x, y) is thus a word on an alphabet that depends onthe integer n, which gives information on how the word [[xi].sub.n](t) is split by the factorization xy. Note that the length of the history [h.sub.n] (t, x, y) is at most rank(t) + 1.

The simplified history [sh.sub.n] (t, x, y) of the factorization [[xi].sub.n] (t) = xy is obtained from the history [h.sub.n] (t, x, y) by replacing each 4-tuple (2, j, k, l) by (2, j). On the other hand, dropping the first two components of each letter of the history [h.sub.n](t, x, y), we obtain a word whose letters are pairs of nonnegative integers, which we identify with an integer vector in even dimension, called the exponent vector. A factorization of [[xi].sub.n] (t) can be recovered from its history but may not be recoverable from its simplified history without the extra information contained in the exponent vector.

Observe that ([[xi].sub.n][(t)).sub.n] converges to [[t].sub.S] in [[??].sub.X]S. We will be interested in sequences ([x.sub.n], [y.sub.n][).sub.n] such that [x.sub.n][y.sub.n] = [[xi].sub.n] (t). We call such a sequence a factorization sequence for t.

It will be convenient in the proofs to work with factorization sequences having additional properties. Note that the set of simplified histories of factorizations of [[xi].sub.n] (t) is finite and depends only on t. Moreover, the dimension of all exponent vectors is bounded by 2 rank(t). Therefore, any factorization sequence for t has a subsequence whose

(a) induced sequence of simplified histories is constant,

(b) induced sequence of exponent vectors belongs to [[??].sup.d] for some constant d and converges in [[??].sup.d] \[[??].sup.d].

We call filtered a sequence with these properties. An application of this notion is the following simple statement.

Lemma 2.1. Let ([x.sub.n], [y.sub.n][).sub.n] be a factorization sequence for a [??]-term. Then both ([x.sub.n][).sub.n] and ([y.sub.n][).sub.n] have subsequences converging in [[??].sub.x] S to 1-words.

Proof: Let t be the 1-term of the statement. By the above, one may assume that the sequence [([x.sub.n], [y.sub.n]).sub.n] is filtered. We proceed by induction on rank(t). The case rank(t) =0 is straightforward. Otherwise, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as in (2.1). There are two cases, according to the first letter of [sh.sub.n](t, x, y), which can be of the form (1, j) or (2, j). Both cases are similar, so assume that it is of the form (1, j). Therefore, the factorization [x.sub.n][y.sub.n] of [[xi].sub.n](t) is given by (2.2), hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By definition, [t.sub.j] is a [??]-term and rank([t.sub.j]) < rank(t), whence by induction [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have subsequences converging to [??]-terms, respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, ([x.sub.n][).sub.n] (resp. ([y.sub.n][).sub.n]) has a subsequence converging to the [??]-term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (resp. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

2.2 Factoriality of some pseudovarieties

A pseudovariety of semigroups is said to be closed under concatenation if the corresponding variety of rational languages has that property. A nontrivial pseudovariety V is closed under concatenation if and only if it contains A, the pseudovariety of aperiodic (or group-free) semigroups, and the multiplication of the profinite semigroup [[bar.[OMEGA]].sub.X] V is an open mapping for every finite alphabet X as proved by Almeida and Costa (2009) based on results of Straubing (1979) (in the monoid case) and Chaubard et al. (2006) (in the semigroup case) characterizing such pseudovarieties in terms of certain algebraic closure properties.

A pseudovariety V is said [sigma]-factorial if, for every finite alphabet X, every factor in [[??].sub.X]M of a [sigma]-word over V is also a [sigma]-word over V. Note that the pseudovariety S is not [kappa]-factorial, since [x.sup.[alpha]] is a prefix of [x.sup.[omega]] for every a [member of] [??].

Theorem 2.2. Let V be a pseudovariety closed under concatenation. Then V is 1-factorial.

Proof: The statement is obvious if V is trivial. Otherwise, let u = vw be a factorization in [bar.[OMEGA]].sub.X]V of an arbitrary element of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let t be a 1-term such that [[t].sub.v] = u. Since the sequence [([[xi].sub.n](t)).sub.n converges to u = vw in [[??].sub.x]V and the multiplication is open in [[??].sub.x]V, for all sufficiently large n, each [[xi].sub n](t) may be factorized as [[xi].sub.n] (t) = [v.sub.n][w.sub.n] in such a way that lim [v.sub.n] = v and lim [w.sub.n] = w.

By Lemma 2.1, both [([v.sub.n]).sub.n] and [([w.sub.n]).sub.n] have subsequences converging, in [[??].sub.X]S, to 1-words over S. Therefore, in [[??].sub.X] V, these subsequences converge to 1-words over V, so that v and w are actually 1-words over V.

For a pseudovariety H of groups, [bar.H] denotes the pseudovariety of all finite semigroups whose subgroups lie in H. In particular, when H is the trivial pseudovariety, then [bar.H] = A. It is a well-known and elementary fact that [bar.H] is always closed under concatenation. Denote by [B.sub.n] the Burnside pseudovariety of all finite groups of exponent dividing n. The pseudovariety [[bar.B].sub.n] is thus defined by the pseudoidentity [x.sup.[omega]+n] = [x.sup.[omega]].

In the following result, the special case n =1, corresponding to the pseudovariety A, was first shown by Almeida et al. (2015) with a much more involved proof.

Corollary 2.3. For every positive integer n the pseudovariety [[bar.B].sub.n] is [kappa]-factorial. In particular, the pseudovariety A is [kappa]-factorial.

Proof: We claim that the equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds for |X| = 1 and so also for every finite alphabet X. Therefore, the result follows from Theorem 2.2. To prove the claim, we show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For this, let a be a 1-exponent and let [([a.sub.[kappa]]).sub.[kappa]] be a sequence of integers converging to [alpha]. One can assume that [a.sub.[kappa]] modulo n is a constant a, hence [a.sub.[kappa]] = [nb.sub.[kappa]] + a, with [b.sub.[kappa]] [member of] [??] for all [kappa]. In [[bar.[OMEGA]].sub.{x}][[bar.B].sub.n], we then have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Another application of Theorem 2.2 is the following result, which is a weaker version of one that was established in (Almeida and Volkov, 2006, Corollary 8.12). Although the original result was formulated for the pseudovariety of all finite semigroups, the proof applies unchanged to pseudovarieties containing all finite local semilattices. Related results, under the same hypothesis as the following corollary, have been obtained by Steinberg (2010).

Corollary 2.4. If |X| [??] 2 and V is a nontrivial pseudovariety closed under concatenation, then there is no 1-word in the minimum ideal of [bar.[OMEGA].sub.X] V.

Proof: Since V is 1-factorial by Theorem 2.2 and since every element of [[??].sub.X]V is a factor of every element of the minimum ideal, if there were a 1-word in the minimum ideal then every element of [[??].sub.X]V would be a 1-word. We claim that this is impossible under the hypothesis that |X| [??] 2.

To prove the claim, observe that by definition, every 1-word of [[bar.[OMEGA]].sub.X]V which is not a word has at least one infinite power of a finite word as an infix. In particular, it admits as factors powers of finite words of arbitrarily large exponent. Thus, it suffices to exhibit an element of [[??].sub.X]V that fails this condition. For this purpose let x, y [member of] X be distinct letters and consider the Prouhet-Thue-Morse substitution, defined by [phi](x) = xy, [phi](y) = yx, and [phi](z) = z for all z [member of] X \ {x, y}. This extends to a unique continuous endomorphism of [[bar.[OMEGA]].sub.X]V, which we also denote [phi]. Since, as proved by Hunter (1983), the monoid of continuous endomorphisms of [[??].sub.X]V is profinite under the pointwise convergence topology, we may consider the element [[phi].sup.[omega]] (x) = lim [[phi].sup.n!](x). Now, it is well known that each word [[phi].sup.n!] (x) is cube free (see, for instance, Lothaire (1983)). Since V is nontrivial and closed under concatenation product, it contains A. Therefore, the sets of the form [([[bar.[OMEGA]].sub.X]V).sup.1]u([[bar.[OMEGA]].sub.X]V[).sup.1], where u is a word, are open (Almeida, 1995, Theorem 3.6.1). Hence, [[phi].sup.[omega]] (x) is also free of cubes of finite words and so [[phi].sup.[omega]](x) is not a 1-word.

3 The Pin-Reutenauer procedure over S for pure signatures

Given a pseudovariety V of semigroups, an implicit signature [sigma] and a subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we denote by [??] the closure of L in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Both the implicit signature [sigma] and the pseudovariety V are understood in this notation. We are interested in computing a representation of such closures in two cases:

(a) when L is of the form pV(K) for some rational subset K of [X.sup.+], where pV is the natural continuous homomorphism from [[??].sub.X]S to [[??].sub.X]V;

(b) when L is a rational subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Recall that the class of rational subsets of a semigroup M is the smallest family of subsets of M containing the empty set and the singletons {m} for m [member of] M, and closed under union (Y, Z) [??] Y + Z, product (Y, Z) [??] YZ = {yz | y [member of] Y, z [member of] Z} and iteration Y [??] Y + = [[union].sub.k[??]1] [Y.sup.k]. Since the homomorphic image of a rational set is rational, any set of the form a is also of the form b. Conversely, there are of course rational sets of [[OMEGA].sup.[sigma].sub.X] [disjunction] that are not obtained as image of a rational set of [X.sup.+] under pV, such as the singletons {[a.sup.[alpha]]} where [alpha] [member of] [??] is a [sigma]-exponent.

We say that the Pin-Reutenauer procedure holds for a class C of subsets of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if, for every K, L [member of] C, the following conditions are satisfied:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.2)

where [<U>.sub.[sigma]] denotes the [sigma]-subalgebra generated by the subset U of [[OMEGA].sup.[sigma].sub.X] [disjunction]. Again, in this notation, the fact that closures are taken in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is understood.

We say that V is (weakly) [sigma]-PR if, for every finite alphabet X, the Pin-Reutenauer procedure holds for the class of all subsets of [[OMEGA].sup.[sigma].sub.X] [disjunction] of the form pV(L) with L [??] [X.sup.+] a rational language. We say that V is strongly [sigma]-PR if, for every finite alphabet X, the Pin-Reutenauer procedure holds for the class of all rational subsets of [[OMEGA].sup.[sigma].sub.X] [disjunction].

In this section, we only deal with the pseudovariety S. In Section 4, we shall transfer our results from S to other pseudovarieties. The main result of this section is the following theorem. It applies only to pure signatures, which we describe below.

Theorem 3.1. The pseudovariety S is [sigma]-PR for every pure unary signature a containing K. The additional purityproperty that a is required to possess is the following.

Definition. A unary signature [sigma] is said to be pure if, for every positive integer d and for all [alpha] [member of] [??], if d[alpha] is a [bar.[sigma]]-exponent, then a is also a [bar.[sigma]]-exponent.

Note that the quotient of d[alpha] by d is actually uniquely determined: if [alpha], [beta] [member of] [??] and d [member of] N {0} are such that d[alpha] = d[beta], then [alpha] = [beta]. This follows immediately from the fact that the free profinite group on one generator, which is isomorphic to [??] \ N, is torsion-free. Let us show this fact directly: d[alpha] = d[beta] means that all finite semigroups satisfy [x.sup.d[alpha]] = [x.sup.d[beta]]. To show that all finite semigroups also satisfy [x.sup.[alpha]] = [x.sup.[beta]], it is sufficient to consider 1-generated semigroups. Such semigroups have presentations of the form [S.sub.m,p] = [??]a: [a.sup.m] = [a.sup.m+p]), for integers m,p [??] 0. Note that the semigroup homomorphism [phi]: [S.sub.m,p] [right arrow] [S.sub.dm,dp] mapping a to [a.sup.d] is injective. Since [S.sub.dm,dp] satisfies [x.sup.d[alpha]] = [x.sup.d[beta]], we have in [S.sub.dm,dp] the equalities [phi]([a.sup.[alpha]]) = [a.sup.d[alpha]] = [a.sup.d[beta]] = [phi]([a.sup.[beta]]), whence [S.sub.m,p] satisfies [x.sup.[alpha]] = [x.[beta]]. This proves that [alpha] = [beta].

In view of the following lemma, Theorem 3.1 can be applied to the signature k.

Lemma 3.2. The unary signature k is pure.

Proof: Every [bar.[kappa]]-exponent is of the form [omega] + n, where n [member of] Z. Therefore, it suffices to show that, if n is an integer, d is a positive integer, and [alpha] [member of] [??] is such that [omega] + n = d[alpha], then d divides n, whence [alpha] = [omega] + n/d is again a [bar.[kappa]]-exponent. For that purpose, consider the unique continuous homomorphism of additive monoids [phi]: [??] [right arrow] [??]/d[??] which maps 1 to 1. We have [phi](w) = [phi]([lim.sub.k] k!) = 0 and [phi](d[alpha]) = d[phi]([alpha]) = 0, and we deduce from the equality [omega] + n = d[alpha] that [phi](n) =0.

To establish Theorem 3.1, we first prove a technical key lemma in Section 3.1. We shall then consider separately the cases of concatenation and iteration respectively in Sections 3.2 and 3.3.

3.1 A key lemma

We first prove a technical result which will be the key lemma in the sequel. It shows that, under suitable hypotheses, one can balance the factors of a factorization of a given [bar.[sigma]]-term to make them [bar.[sigma]]-terms themselves, without affecting membership in given clopen sets. For L [??] [X.sup.+], we denote by cl(L) the topological closure of L in [[??].sub.X]S.

Given 1-terms [t.sub.1],..., [t.sub.m] and languages [L.sub.1];..., [L.sub.m], we say that ([t.sub.1],..., [t.sub.m]) is a ([L.sub.1];..., [L.sub.m])-splitting of a 1-term t if the following conditions hold:

(i) t = [t.sub.1] ... [t.sub.m];

(ii) [[t.sub.i]]s [member of] cl([L.sub.i]) for every i = 1,..., m.

Given a [sigma]-term t, let [[lambda].sub.[sigma]] (t) = ([rank.sub.[sigma]] (t), [v.sub.[sigma]] (t)). We may write [lambda] instead of [[lambda][sigma]] when [sigma] is clear from the context.

Lemma 3.3. Let [sigma] be a unary signature containing k, let t be a [??]-term, and let [L.sub.1],..., [L.sub.m] be rational languages. If t admits an ([L.sub.1],..., [L.sub.m])-splitting ([t.sub.1],..., [t.sub.m]), then there exists a [??]-term z admitting an ([L.sub.1],..., [L.sub.m])-splitting ([z.sub.1],..., [z.sub.m]) such that:

(1) [[z].sub.S] = [[t].sub.S],

(2) [z.sub.j] is a [??]-term for i = 1,..., m,

(3) [[lambda].sub.[sigma]] ([Z.sub.i]) = [[lambda].sub.1] ([t.sub.i]) for i = 1,..., m.

Proof: We only prove the statement for m = 2, since it is representative of the general case, and it allows a simplified notation.

Let ([t.sub.1], [t.sub.2]) be an ([L.sub.1], [L.sub.2])-splitting of t. Set [x.sub.n] = [[xi].sub.n]([t.sub.1]) and [y.sub.n] = [[xi].sub.n]([t.sub.2]). By ii, lim [x.sub.n] = [[t.sub.1]]s belongs to cl([L.sub.1]), which is open by rationality of [L.sub.1] (Almeida, 1995, Thm. 3.6.1). Therefore, the word [x.sub.n] belongs to [L.sub.1] for all sufficiently large n. Similarly, the word [y.sub.n] belongs to [L.sub.2] for all sufficiently large n. Let [phi]: [X.sup.+] [right arrow] S be a homomorphism into a finite semigroup recognizing both languages [L.sub.1] and [L.sub.2]. In view of i, [([x.sub.n],[y.sub.n]).sub.n] is a factorization sequence for t. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a filtered subsequence of [([x.sub.n], [y.sub.n]).sub.n], and let [([k.sub.1,r], [[??].sub.1,r],..., [k.sub.d,r], [[??].sub.d,r]).sub.r] be the sequence of exponent vectors forthe factorization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When [([k.sub.i,r]).sub.r] (resp. [([[??].sub.i,r]).sub.r]) is constant, let [k.sub.i] (resp. [[??].sub.i]) be this constant value. Otherwise, by taking a subsequence, we may assume that for each s [member of] S, each of the sequences [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is constant, say with value respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the integers [k.sub.i] and [l.sub.i] being independent of the element s [member of] S.

In view of Case (2.3) of the definition of factorization sequence and since t is a [bar.[sigma]]-term, each sequence [([k.sub.i,r] + [[??].sub.i,r] + 1).sub.r] converges to some [bar.[sigma]]-exponent [[gamma].sub.i]. In particular, [[gamma].sub.i] is infinite. Define ([[alpha].sub.i], [[beta].sub.i]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that in all cases, we have

[[alpha].sub.i] + [[beta].sub.i] + 1 = [[gamma].sub.i]. (3.3)

Let [z.sub.1] (resp. [z.sub.2]) be the 1-term obtained from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (resp. from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) by replacing for every i the exponent [k.sub.i,r] by [[alpha].sub.i] and the exponent [[??].sub.i,r] by [[beta].sub.i]. Set

z = [z.sub.1][z.sub.2],

and let us verify that [z.sub.1], [z.sub.2] and z fulfill the desired properties. We have to show properties 1-3, and that ([z.sub.1], [z.sub.2]) is an ([L.sub.1], [L.sub.2])-splitting of z.

First note that, by (3.3), we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all 1-term y. Since ([k.sub.i,r] + [[??].sub.i,r] + 1[).sub.r] converges to [[gamma].sub.i], using (2.3) we deduce that [[z].sub.S] = [[t].sub.S], which proves 1. Next, by definition [[alpha].sub.i] and [[beta].sub.i] either belong to N, or are of one of the forms [[gamma].sub.i] - n or [omega] + n where n [member of] [??]. Since [[gamma].sub.i] is a [??]-exponent and since [sigma] contains k, both [[alpha].sub.i] and [[beta].sub.i] are [bar.[sigma]]-exponents, whence both [z.sub.1], [z[beta].sub.2] are [??]-terms, which proves 2. Finally, we have [[lambda].sub.[??]] ([z.sub.i]) = [[lambda].sub.[??]] ([t.sub.i]) by construction, which is 3.

It remains to verify that ([Z.sub.1], [Z.sub.2]) is an ([L.sub.1], [L.sub.2])-splitting of z. Condition i is satisfied by definition of z. Let us verify that [z.sub.1] [member of] cl([L.sub.1]) (showing that [z.sub.2] [member of] cl([L.sub.2]) is similar). Let [??]: [[??].sub.X]S [right arrow] S be the continuous extension of [phi] to [[??].sub.X]S. By ii applied to the ([L.sub.1], [L.sub.2])-splitting ([t.sub.1], [t.sub.2]) of t, we have [t.sub.1] [member of] cl([L.sub.1]) = [[??].sup.-1]([phi]([L.sub.1])). Since [t.sub.1] is the limit of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it suffices to show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This follows from the claim that for r large enough, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is clear if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is constant, while it is obtained by reasoning in the group {[s.sup.[omega]+p] | p [??] 0} if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is unbounded.

3.2 The case of concatenation

We are now ready to treat the case of concatenation, that is, to establish Property (3.1).

Theorem 3.4. Equality (3.1) holds over the pseudovariety S for every unary signature [sigma] containing k and for all rational languages K, L [??] [X.sup.+].

Proof: The inclusion from right to left in (3.1) amounts to continuity of multiplication in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and thus it is always valid. For the direct inclusion, let v be an arbitrary element of [??]. We need to show that v belongs to [bar.K] [??] [bar.L].

Choose a [sigma]-term t such that [[t].sub.S] = v. Since v [member of] cl(KL) and since the closure cl(KL) of the rational language KL is clopen (Almeida, 1995, Thm. 3.6.1), the word [[xi].sub.n](t) belongs to KL for all sufficiently large n. For such n, let [t.sub.1,n] [member of] K and [t.sub.2,n] [member of] L be words such that [[xi].sub.n](t) = [t.sub.1,n][t.sub.2,n], and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a filtered subsequence of [([t.sub.1,n], [t.sub.2,n]).sub.n]. For i = 1, 2, let [t.sub.i] be the term obtained by substituting each exponent vector with the limit of the sequence of exponent vectors, in [[??].sup.d], so that lim [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and ([t.sub.1], [t.sub.2]) is a (K, L)-splitting of t. By Lemma 3.3, it follows that there exists a [??]-term z suchthat v = [[z].sub.S] and z admits a (K, L)-splitting ([z.sub.1], [z.sub.2]) into [bar.[sigma]]-terms. Since the unary signature [sigma] contains k, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by Remark 1. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and similarly [[z.sub.2]]s [member of] [??]. Finally, v = [[z].sub.S] = [[z.sub.1][z.sub.2]]S = [[z.sub.1]]S * [[z.sub.2]]S [member of] [??] * [??].

3.3 The case of iteration

We now show that (3.2) holds over the pseudovariety S, for every pure implicit signature [sigma] containing [kappa] and every rational language L [??] [X.sup.+]. It is easy to see that the inclusion from right to left in (3.2) always holds, see Almeida et al. (2014). The rest of this subsection is devoted to the proof of the other inclusion.

Theorem 3.5. Equality (3.2) holds over the pseudovariety S for every pure unary signature [sigma] containing k and for every rational language L [??] [X.sup.+].

The proof of Theorem 3.5 follows the lines of its analog for the pseudovariety A which is presented in (Almeida et al., 2014, Section 6), even though the argument requires significant changes in several points.

Consider an element v of [bar.[L.sup.+]]. We must show that there is a [sigma]-term which coincides with v when evaluated on (finitely many) suitable elements of [??]. It turns out to be convenient to assume more generally that v [member of] [cl.sub.[sigma]] ([L.sup.+]), so that there exists a [??]-term t suchthat [[t].sub.S] = v. Therefore, we want to show that, for every [??]-term t,

for every rational language L, [[t].sub.s] [member of] [bar.[L.sup.+]] implies [[t].sub.S] [member of] [<[bar.[L.sup.+]]>.sub.[sigma]]. ([P.sub.t])

Let [w.sub.k] = [[xi].sub.k](t). The sequence of words [([w.sub.k]).sub.k] converges to v = [t]s in [[??].sub.X]S. As v belongs to the open set [bar.[L.sup.+]], the word [w.sub.k] belongs to [L.sup.+] for all sufficiently large k, and we may therefore assume that there are factorizations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.4)

with each [w.sub.i,j] [member of] L. If there is a bounded subsequence of the sequence [([r.sub.k]).sub.k], which counts the number of factors from L, then Theorem 3.4 yields that v belongs to the subsemigroup of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] generated by [??] and we are done. We may therefore assume that lim [r.sub.k] = [infinity], which implies that rank (t) [??] 1. We first reduce the problem to the case v (t) = 1.

Proposition 3.6. Assume that ([P.sub.t]) holds for every [??]-term t with V (t) = 1. Then, it holds for every [??]-term t.

Proof: Lett be a [bar.[sigma]]-term such that V(t) > 1. Let v = [[t].sub.S], and assume that v [member of] [bar.[L.sup.+]]. Toshowthat v [member of] [<[bar.L]>.sub.[sigma]], we proceed by induction on [lambda](t), for the lexicographical order on [??] X [??]. Consider the factorization of t in [bar.[sigma]]-terms as in (2.1) and the factorization (3.4) of [w.sub.k] = [[xi].sub.k] (t). We distinguish three cases.

Case 1 Suppose first that there are infinitely many indices k for which there exists [i.sub.k] [member of] {1,..., [r.sub.k]} such that the first letter of the simplified history

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is of one of the forms (1, j) with 0 [not equal to] j [not equal to] m, or (2, j) with 1 [not equal to] j [not equal to] m. That is, the corresponding factorizations ([x.sub.k], [y.sub.k]), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], do not split [[xi].sub.k](t) in its prefix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], nor in its suffix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Lemma 2.1, both [([x.sub.k]).sub.k] and [([y.sub.k]).sub.k] admit subsequences converging to 1-words, say [u.sub.1] = [[[u.sub.1]].sub.S] and [u.sub.2] = [[[u.sub.2]].sub.S] respectively, with [u.sub.1][u.sub.2] = t. Since both [x.sub.k] and [y.sub.k] belong to [L.sup.+], we deduce that [u.sub.1], [u.sub.2] [member of] cl([L.sup.+]). Therefore, one can apply Lemma 3.3: there exist [??]-terms [z.sub.1][z.sub.2] such that v = [[[z.sub.1][z.sub.2]].sub.S], and for i = 1, 2, [lambda]([z.sub.i]) = [lambda]([u.sub.i]) and [[[z.sub.i]].sub.S] [member of] cl([L.sup.+]). By Remark 1, we obtain [[[z.sub.i]].sub.S] [member of] [??]. By the assumption on the first letter of the simplified histories, we have rank([u.sub.i]) = rank(t) and V([u.sub.i]) < V(t), hence [lambda]([z.sub.i]) = [lambda]([u.sub.i]) < [lambda](t) (i = 1, 2). Arguing inductively, we deduce that [[[z.sub.i]].sub.S] and [[[z.sub.2]].sub.S] belong to [[??].sub.[sigma]], whence so does v = [[[z.sub.1][z.sub.2]].sub.S] = [[[z.sub.1]].sub.S] * [[[z.sub.2]].sub.S]- This concludes the proof for Case 1.

Case 2 Assume now that for all sufficiently large k, there is an index [i.sub.k] such that the first letters of the simplified histories

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

are of the forms (1,0) or (2,1) for the first one, and (1, m) or (2, m) for the second one. In other words, the factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] jumps from the prefix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to the suffix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As in the first case, we may apply twice Lemma 2.1 to obtain from the following sequence of factorizations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

an ([L.sup.+], L, [L.sup.+])-splitting of t into [??]-terms, say t = [u.sub.1][u.sub.2][u.sub.3]. Applying Lemma 3.3, we deduce that there exists an ([L.sup.+], L, [L.sup.+])-sphtting ([z.sub.1], [z.sub.2], [z.sub.3]) into [??]-terms of a [??]-term z such that [[z].sub.S] = v and [lambda]([z.sub.i]) = [lambda]([u.sub.i]), i = 1,2,3. By Remark 1, we obtain [[[z.sub.i]].sub.S], [[[Z.sub.3]].sub.S] [member of] [??] and [[[z.sub.2]].sub.S] [member of] [bar.L]. By the hypothesis of Case 2, we know that for i = 1, 3, we have either rank([u.sub.i]) = rank(t) and V([u.sub.i]) = 1, or rank([u.sub.i]) < rank(t). Hence, [lambda]([z.sub.i]) < [lambda](t). Thus, we may apply the induction hypothesis to deduce that [[[z.sub.i]].sub.S] and [[z.sub.3][].sub.S] belong to [<[bar.L]>.sub.[sigma]]. Hence, we finally have v = [[[z.sub.i]].sub.S] * [[[z.sub.2]].sub.S] * [[[z.sub.3]].sub.S] [member of] [[??].sub.[sigma]] * [??] * [[??].sub.[sigma]] [??] [[??].sub.[sigma]].

Case 3 Assume finally that for all sufficiently large k and for all indices [i.sub.k], the first letter of the simplified history [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is

(a) either of the form (1,0) or (2,1), which means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] spans from the prefix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to the end of [[xi].sub.k](t),

(b) or of the form (1, n) or (2, n), which means that [w.sub.1,k] jumps from the beginning of [[xi].sub.k] (t) to the suffix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This case is treated as Case 2, setting [v.sub.3] (resp. [v.sub.1]) to be the empty term, in case a or b occurs.

To conclude the proof of Theorem 3.5, it remains to treat the case where V(t) = 1. For dealing with this case, we use directed weighted multigraphs. A (multi)graph is a tuple (Q, [([E.sub.p,q]).sub.(P,q)[member of]QXQ]) where Q is a set of vertices, and [E.sub.p,q] is a set of edges having source p and target q, for each pair of vertices (p, q) [member of] Q X Q. In the sequel, the graphs shall always be finite. A weighted multigraph is given by a multigraph together with a weight function, which associates to each edge e a nonnegative integer w(e). If e is an edge with source p and target q, we represent this edge by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For a path [gamma] of a graph [GAMMA], let c([gamma]) denote the edge-induced subgraph of [GAMMA] whose edges are those traversed by [gamma]. We call c([gamma]) the support of [gamma]. Furthermore, if [zeta] is an edge of [GAMMA], then |[gamma]|[zeta] denotes the number of times [gamma] goes through the edge [zeta]. For a subgraph [GAMMA]' of [GAMMA], we denote by |[gamma]|[GAMMA]' the minimum of |[gamma]|[ZETA] with [zeta] an arbitrary edge of [GAMMA]'.

Lemma 3.7. Let [([[pi].sub.k]).sub.k] be a sequence of paths of a finite multigraph [GAMMA]. If there is some edge [zeta] for which the sequence [(|[[pi].sub.k] [|.sub.[zeta]]).sub.k] is unbounded, then there is some cycle [gamma] such that [(|[[pi].sub.k][|.sub.c([gamma])]).sub.k] is unbounded.

Proof: Consider on each path [[pi].sub.k] the subpaths which start with the edge [zeta] and whose length is the total number of vertices of the graph [GAMMA]. Since there are only finitely many such subpaths, at least one of them, say [delta], must be used an unbounded number of times. Because [delta] must go at least twice through the same vertex, [delta] contains some cycle which satisfies the required condition.

We conclude the proof of Theorem 3.5 by establishing the following result, which, combined with Proposition 3.6, implies that Property ([p.sub.t]) holds for every [bar.[sigma]]-term t.

Proposition 3.8. Property ([p.sub.t]) holds for every [bar.[sigma]]-term t with V(t) = 1.

Proof: Let t be a [??]-term with V(t) = 1. Let w = [[t].sub.S]. Assuming that w [member of] [??], we want to show that w [member of] [[??].sub.[sigma]]. We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with rank([t.sub.o]), rank([t.sub.1]) [??] rank([s.sub.1]) = rank(t) - 1. Let [w.sub.k] = [[xi].sub.k](t). Since for k large enough, we have [w.sub.k] [member of] [L.sup.+], one may consider a factorization (3.4) of [w.sub.k]. Using a similar argument as in the proof of Case 2 of Proposition 3.6, we may assume, replacing [([w.sub.k]).sub.k] by a subsequence if necessary, that [[xi].sub.k] ([t.sub.0]) is a prefix of [w.sub.1,k] and [[xi].sub.k] ([t.sub.1]) is a suffix of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since L is a rational language of [X.sup.+], there is a homomorphism [phi]: [X.sup.*] [right arrow] M onto a finite monoid M such that [[phi].sup.-1] (1) = {1} and [[phi].sup.-1] ([phi](L)) = L. Let m and p be positive integers such that

[a.sup.m+p] = [a.sup.m] for every a [member of] M. (3.5)

We construct for each k a finite directed multigraph [[GAMMA].sub.k]. The set of vertices is

[V.sub.k] = {(a,b) [member of] M X M: [[xi].sub.k] ([s.sub.1]) [member of] [[phi].sup.-1](a)[L*][[phi].sup.-1](b)} [union] {^,$},

where the two symbols ^ and $ do not belong to M. The following are the edges of the graph [[GAMMA].sub.k], where e denotes a natural number that does not exceed [[xi].sub.k] ([[alpha].sub.1]):

* there is an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

* there is an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

* there is an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Observe that, in view of (3.5), there is an edge in the graph of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with e [??] m if and only if there is also an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and e + p [??] [[xi].sub.k] ([[alpha].sub.1]).

The purpose of this graph is to capture factorizations of the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belonging to [L.sup.+]. More precisely, for each k, the factorizations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.6)

determine a path [[pi].sub.k] from vertex ^ to vertex $: the factors [w.sub.i,k] which are not completely contained in some factor [[xi].sub.k]([s.sub.1]) determine the edges. Each intermediate vertex in the path corresponds to a factor [[xi].sub.k] ([s.sub.1]) together with a factorization into a word, followed by a possibly empty product of elements from L, followed by a word, where only the values under [phi] of the prefix and suffix words are relevant.

Conversely, every path [gamma] from ^ to $ determines a factorization of a word of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] into a product of elements of L. Indeed, we may choose for each intermediate vertex q words [u.sub.q],k, [v.sub.q],k [member of] [X.sup.*] and [z.sub.q],k [member of] [L*] suchthat

[[xi].sub.k]([s.sub.1]) = [u.sub.g,k][z.sub.q,k][v.sub.qq,k]. (3.7)

Then, for each edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the word

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.8)

Belongs to L. If the path [gamma] is the sequence of edges ([[zeta].sub.0], [[zeta].sub.1],..., [[zeta].sub.r]),with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we also have words

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in L. Then the following is the factorization associated with the path:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.9)

The total number [??] of factors [[xi].sub.k]([s.sub.1]) that are covered by following the path [gamma] is the sum of the weights of the edges, taking into account multiplicities; we call it the total weight of the path. Combining with Euler's Theorem (Almeida, 1995, Theorem 5.7.1), it is now easy to deduce that each of the following transformations does not change the total weight of a path and therefore the value of the left side of the equality (3.9):

1. to traverse the edges in a path in a different order, without changing the number of times we go through each edge;

2. suppose that in the support of the path there are two cycles [[delta].sub.1] and [[delta].sub.2], with respective total weights [n.sub.1] and [n.sub.2], and that the positive integers [r.sub.1] and [r.sub.2] are such that [n.sub.1][r.sub.1] = [n.sub.2][r.sub.2]; suppose further that the path goes through each edge in ([[delta].sub.i] more than [r.sub.i] times; to replace the path by another one which goes through each edge in ([[delta].sub.1] less [r.sub.1] times than before and through each edge in ([[delta].sub.2] more [r.sub.2] than before;

3. if there are two edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the path with both [e.sub.1], [e.sub.2] [??] m, to replace in the path one occurrence of the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by that of the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], provided we compensate by replacing one occurrence of the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

4. suppose that in the support of the path there is a cycle (with total weight n and that the path goes through each edge in [delta] at least p + 1 times; suppose further that there is an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with weight at least m; replace the path by another one which goes through each edge in [delta] less p times than before and change the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Using transformations of type 3, we may assume that the path [[pi].sub.k] goes through at most one edge whose weight exceeds m + p - 1. Therefore, the remaining edges in [[pi].sub.k] are taken from a fixed finite set. Thus, by taking a subsequence, we may further assume that all paths [[pi].sub.k] use exactly the same edges of weight at most m + p - 1 and, either none of the [[pi].sub.k] use any other edges or, otherwise they all use only one additional edge [[zeta].sub.k] connecting two fixed vertices. Hence all the graphs c([[pi].sub.k]) are the same finite graph, up to an isomorphism that only changes one edge.

On the other hand, using transformations of type 4, we may assume that if all the paths [[pi].sub.k] go through some edge of weight at least m, then the graph c([[pi].sub.k]) contains no cycle in which every edge is used at least p + 1 times.

We now split the argument into two cases. Suppose first that every c([[pi].sub.k]) contains an edge of weight at least m. In this case, one can apply Lemma 3.7 to deduce that there is a bound on the length of the paths [[pi].sub.k] and, therefore, we may assume that they all have the same length. Moreover, we may further assume that, except for the edge [[zeta].sub.i,k], at the same position i, all paths [[pi].sub.k] = ([[zeta].sub.0],..., [[zeta].sub.i-1], [[zeta].sub.i,k], [[zeta].sub.i+1],..., [[zeta].sub.r]) are identical. Consider the factorizations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

of the form (3.9) associated with each of the paths [[pi].sub.k].

Let [e.sub.j] be the weight of each edge [[zeta].sub.j] (j [not equal to] i) and let [e.sub.j,k] be the weight of the edge [[zeta].sub.i,k]. Computing the total weight, we obtain the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.10)

Letting k [right arrow] [infinity] in (3.10), we deduce that lim [e.sub.i,k] = [[alpha].sub.1] - [[summation].sub.j[not equal to]i] [e.sub.j] and, therefore, [e.sub.i] = lim [e.sub.i,k] is a [??]-exponent, since so is [[alpha].sub.1] and since by definition, [??] is complete.

According to (3.8), the factors [y[zeta].sub.j],k with j [??] {0, i, r} are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By compactness of [[??].sub.X]S, we may assume that each of the sequences ([[u.sub.g],k).sub.k], [([v.sub.q],k).sub.k], and [([z.sub.q],k).sub.k] converges to the respective limit [u.sub.q], [v.sub.q], and [z.sub.q] (q = q[[zeta].sub.1],..., q[[zeta].sub.r]). Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then we obtain a factorization

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in which each [y.sub.j] belongs to cl(L), while the [z.sub.q] belong to cl([L.sup.+]) [union] {1}. By Lemma 3.3, we may assume that each [u.sub.q], [v.sub.q], and [z.sub.q] is a 1-word. By definition (3.7) of the words [z.sub.q,k], the latter has rank less than rank(w). It follows that so is each [y.sub.j]. Hence the [y.sub.j]'s belong to [??] and the [z.sub.q] belong to [??] [union] {1}. By the induction hypothesis, each [z.sub.q] belongs to [[??].sub.[sigma]]. Hence, w belongs to [[??].sub.[sigma]], which completes the proof of the first case.

It remains to consider the case where all edges have weight less than m. By previous reductions, we know that the graph c([[pi].sub.k]) is constant. Because the total weight tends to [infinity], so does the length of the path [[pi].sub.k]. By Lemma 3.7, there is some simple cycle [gamma] for which the sequence (|[[pi].sub.k] [|.sub.c([gamma])][).sub.k] is unbounded. Applying transformations of type 2, we may assume that there is only one such cycle. By Lemma 3.7, we deduce that the paths 5 with c([delta]) [??] c([[pi].subk]) which go at most once through each edge in c([gamma]) have bounded length. Hence, using transformations of type 1, we may assume that there is a path [delta] from ^ to $ such that the path [[pi].sub.k] is obtained by inserting the power cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at a fixed vertex in the path [delta], say [[pi].sub.k] is the concatenated path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let the total weights of the paths [[delta].sub.i] and [gamma] be respectively [n.sub.i] and n. Then the total weight of the path [[pi].sub.k] is given by the formula

[[xi].sub.k] ([[alpha].sub.1]) = [n.sub.0] + [n.sub.1] + [[n][??].sub.k]. (3.11)

By taking a subsequence, we may assume that the sequence [([[??].sub.k]).sub.k] converges to some [beta] [member of] [??]. From (3.11), it follows that n[beta] = [[alpha].sub.1] - [n.sub.0] - [n.sub.1] Since the signature [sigma] is assumed to be pure, we deduce that [beta] is a [??]-exponent.

By the argument in the preceding case, using the induction hypothesis, each of the paths [[delta].sub.i] and [gamma] determines a corresponding element of [[??].sub.[sigma]], say respectively [y.sub.i] and y, such that w = [y.sub.0][y.sup.[beta]][y.sub.1]. Since [beta] is a [bar.[sigma]]-exponent, we may now end the proof by observing that it follows that w [member of] [[??].sub.[sigma]].

4 Pin-Reutenauer versus fullness

In this section, we apply the main results of Section 3 to show that the Pin-Reutenauer procedure is valid for many pseudovarieties. For this purpose, we establish relationships between that property and fullness, a notion introduced by Almeida and Steinberg (2000a). See also Almeida and Steinberg (2000b); Almeida et al. (2014) for related properties and other applications of fullness.

Recall that pV denotes the natural continuous homomorphism from [[bar.[OMEGA]].sub.X]S to [[bar.[OMEGA]].sub.X]V. The pseudovariety V is said to be full with respect to a class C of subsets of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if the following equality holds for every L [member of] C:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](4.1)

The closure of the left hand side of (4.1) is taken in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], while the closure of the right hand side is taken in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We say that V is (weakly) [sigma]-full if, for every finite alphabet X, V is full with respect to the set of all rational languages of [X.sup.+]. We also say that V is strongly [sigma]-full if, for every finite alphabet X, V is full with respect to the class of all rational subsets of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.1 The general case

We first consider the case of arbitrary pseudovarieties and signatures.

Proposition 4.1. Let a be an arbitrary implicit signature, V be a pseudovariety, and C be the closure under the rational operations of some set of finite subsets of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If the Pin-Reutenauer procedure holds for C, then V is full with respect to C.

Proof: Let L be an arbitrary member of C. We need to show that the equality (4.1) holds. The inclusion from left to right is an immediate consequence of the continuity of the mapping pV. For the reverse inclusion, we proceed by induction on the construction of a rational expression of L in terms of finite sets in G. If L is a finite set, then pV{[bar.L]) = pV(L) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and so the equality (4.1) is trivially verified. Suppose next that [L.sub.1] and [L.sub.2] are elements of C for which the equality (4.1) holds. Since topological closure and the application of mappings commutes with union, the equality (4.1) also holds for L = [L.sub.1] [union] [L.sub.2]. On the other hand, we have the following equalities and inclusions:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] since the Pin-Reutenauer procedure holds for C

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the induction hypothesis

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] since pV is a homomorphism

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by continuity of multiplication.

Taking into account that pV is a homomorphism of [sigma]-semigroups and that the inclusion from right to left in (3.2) always holds (see the paragraph preceding Theorem 3.5, p. 12), one can similarly show that (4.1) holds for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following is an immediate application of Proposition 4.1.

Corollary 4.2. Let [sigma] be an arbitrary implicit signature and V a pseudovariety. If V is (strongly) [sigma]-PR then V is (respectively strongly) [sigma]-full.

The weak version of the following result is proved in (Almeida et al., 2014, Proposition 3.2). The same proof applies to the strong case.

Proposition 4.3. Let V and W be two (strongly) [sigma]-full pseudovarieties such that V [?] W. If W is (respectively strongly) [sigma]-PR, then so is V.

Note that S is trivially [sigma]-full for every implicit signature a. Combining Theorem 3.1 with Corollary 4.2 and Proposition 4.3, we obtain the following result.

Corollary 4.4. Let [sigma] be a pure unary signature containing K. Then a pseudovariety V is [sigma]-PR if and only if it is [sigma]-full.

We do not know whether the hypothesis on the signature can be dropped in Corollary 4.4.

4.2 The group case

We now consider the case of pseudovarieties of groups, for the signature k.

Recall that a group is LERF (locally extendible residually unite) if every finitely generated subgroup is closed in the profinite topology. We say that a pseudovariety of groups H is LERF if, for every finite alphabet X, the relatively free group [[OMEGA].sup.[kappa].sub.x] H is LERF. By a classical result of Hall (1950), the pseudovariety G of all finite groups is LERF.

By (Margolis et al., 2001, Proposition 2.9), G is in fact the only nontrivial extension-closed pseudovariety of groups that is LERF. On the other hand, it is easy to check that, for the pseudovariety Ab of all finite Abelian groups, every subgroup of [[OMEGA].sup.[kappa].sub.x] Ab is closed (Delgado, 1998, Proposition 3.8).

A slightly different notion of strongly [kappa]-PR pseudovariety was considered by Pin and Reutenauer(1991) and Delgado (2001) (where it is simply called PR). Instead of property (3.2), the following property is considered:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.2)

Compared to (3.2), the topological closure in the right hand side of (4.2) has been dropped. As observed in (Almeida et al., 2014, end of Section 4), Equation (4.2) fails for the pseudovariety S and the implicit signature k, for L = [a.sup.+][b.sup.+], since [a.sup.[omega]]b [member of] [bar.[L.sup.+]]\ [<L>.sub.[sigma]]. However, the two notions coincide for the pseudovariety G (Pin and Reutenauer, 1991, Theorem 2.4). With same argument, we generalize this result to LERF pseudovarieties.

Lemma 4.5. Let V be a pseudovariety. If V satisfies (4.2) for a subset L of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then (3.2) also holds. If V is a LERF pseudovariety of groups and [sigma] = k, then (4.2) holds for rational subsets L of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Since for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the inclusions [<L>.sub.[sigma]] [??] [[??].sub.[sigma]] [??] [??] always hold, it is clear that (4.2) implies (3.2).

For the second part, we argue as in (Almeida et al., 2014, p. 4). Let L be a rational subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, [<L>.sub.k] = (L[union][L.sup.-1])+ is rational in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By a well-known theorem of Anissimow and Seifert (1975), the subgroup [<L>.sub.k] is therefore finitely generated. Hence, [<L>.sub.k] is closed in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], by the assumption that V is a LERF pseudovariety. Finally, we have [L.sup.+] [??] [<L>.sub.k], hence [[??] [??] [<L>.sub.k], which, combined with the reverse inclusion, which always holds, yields the result.

It can be shown easily that a k-PR pseudovariety of groups is LERF (see Delgado (1997)). Thus, a pseudovariety of groups is strongly k-PR if and only if it is PR in the sense of Delgado (2001). In (Delgado, 2001, Corollary 3.9), it is also established that every "weakly PR" pseudovariety of groups is k-full, a result which is considerably improved in the present paper, in the form of Corollaries 4.2 and 4.4.

It was conjectured by Pin and Reutenauer (1991) that G is strongly k-PR. Their conjecture was reduced to another conjecture, namely that the product of finitely many finitely generated subgroups of a free group is closed. The latter conjecture was established by Ribes and Zalesskii (1993). Combining with Proposition 4.3 and Corollary 4.2, we obtain the following result.

Theorem 4.6. A pseudovariety of groups is strongly k-PR if and only if it is strongly k-full.

The diagram in Fig. 1 summarizes the results of this subsection. We say that a pseudovariety of groups H is strong RZ if in every finitely generated free H-group, any finite product of finitely generated subgroups is closed. We say that H is weak RZ if, in every finitely generated free H-group, any finite product of finitely generated closed subgroups is also closed.

[FIGURE 1 OMITTED]

References

J. Almeida. Implicit operations on finite [??]-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra, 69(3):205-218, 1991.

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

J. Almeida. Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen, 54 Suppl.:531-552, 1999.

J. Almeida. Finite semigroups: an introduction to a unified theory of pseudovarieties. In G. M. S. Gomes, J.-E. Pin, and P. V. Silva, editors, Semigroups, Algorithms, Automata and Languages, pages 3-64, Singapore, 2002. World Scientific.

J. Almeida. Profinite semigroups and applications. In V. B. Kudryavtsev and I. G. Rosenberg, editors, Structural Theory of Automata, Semigroups, and Universal Algebra, volume 207 of NATO Science Series II: Mathematics, Physics Chemistry, New York, 2005. Springer. Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra, Montreal, Quebec, Canada, 7-18 July 2003.

J. Almeida and A. Costa. Infinite-vertex free profinite semigroupoids and symbolic dynamics. J. Pure Appl. Algebra, 213:605-631, 2009.

J. Almeida and B. Steinberg. On the decidability of iterated semidirect products and applications to complexity. Proc. London Math. Soc., 80:50-74, 2000a.

J. Almeida and B. Steinberg. Syntactic and global semigroup theory, a synthesis approach. In J. C. Birget, S. W. Margolis, J. Meakin, and M. V. Sapir, editors, Algorithmic Problems in Groups and Semigroups, pages 1-23. Birkhauser, 2000b.

J. Almeida and M. V Volkov. Subword complexity of profinite words and subgroups of free profinite semigroups. Int. J. Algebra Comput., 16(2):221-258, 2006.

J. Almeida and M. Zeitoun. The equational theory of [omega]-terms for finite R-trivial semigroups. In M. Branco and G. Gomes, editors, Semigroups and Languages, pages 1-23. World Scientific, 2004.

J. Almeida and M. Zeitoun. An automata-theoretic approach to the word problem for [omega]-terms over r. Theoret. Comput. Sci., 370(1-3):131-169, 2007.

J. Almeida, J. C. Costa, and M. Zeitoun. Tameness of pseudovariety joins involving R. Monatsh. Math., 146:89-111, 2005.

J. Almeida, J. C. Costa, and M. Zeitoun. Closures of regular languages for profinite topologies. Semigroup Forum, 89:20-40, 2014.

J. Almeida, J. C. Costa, and M. Zeitoun. McCammond normal forms for free aperiodic semigroups revisited. LMSJ. Comput. Math., 18:130-147, 2015.

A. W. Anissimow and F. D. Seifert. Zur algebraischen Charakteristik der durch kontext-freie Sprachen definierten Gruppen. Elektron. Informationsverarbeit. Kybernetik, 11(10-12):695-702, 1975.

C. J. Ash. Inevitable graphs: a proof of the type II conjecture and some related decision procedures. Int. J. Algebra Comput., 1:127-146, 1991.

K. Auinger. A new proof of the Rhodes type II conjecture. Int. J. Algebra Comput., 14:551-568, 2004.

K. Auinger. On the decidability of membership in the global of a monoid pseudovariety. Int. J. Algebra Comput., 20(2):181-188, 2010.

K. Auinger and B. Steinberg. On the extension problem for partial permutations. Proc. Amer. Math. Soc., 131:2693-2703, 2003.

K. Auinger and B. Steinberg. A constructive version of the Ribes-Zalesskii product theorem. Math. Z., 250:287-297, 2005.

L. Chaubard, J.-E. Pin, and H. Straubing. Actions, wreath products of C-varieties and concatenation product. Theor. Comp. Sci., 356:73-89, 2006.

J. C. Costa. Free profinite locally idempotent and locally commutative semigroups. J. Pure Appl. Algebra, 163(1):19-47, 2001.

J. C. Costa and M. L. Teixeira. Tameness of the pseudovariety LSl. Int. J. Algebra Comput., 14:627-654, 2004.

M. Delgado. The type II theorem and hyperdecidability of pseudovarieties of groups. PhD thesis, Univ. Porto, 1997. In Portuguese.

M. Delgado. Abelian poinlikes of a monoid. Semigroup Forum, 56:339-361, 1998.

M. Delgado. On the hyperdecidability of pseudovarieties of groups. Int. J. Algebra Comput., 11:753-772, 2001.

M. Hall. A topology for free groups and related groups. Ann. of Math., 52:127-139, 1950.

K. Henckell. Pointlike sets: the finest aperiodic cover of a finite semigroup. J. Pure Appl. Algebra, 55: 85-126, 1988.

K. Henckell, S. W. Margolis, J.-E. Pin, and J. Rhodes. Ash's type II theorem, profinite topology and Malc'ev products. I. Int. J. Algebra Comput., 1:411-436, 1991.

B. Herwig and D. Lascar. Extending partial automorphisms and the profinite topology on free groups. Trans. Amer. Math. Soc., 352:1985-2021, 2000.

R. P. Hunter. Some remarks on subgroups defined by the Bohr compactification. Semigroup Forum, 26: 125-137, 1983.

M. Huschenbett and M. Kufleitner. Ehrenfeucht-Fraisse Games on Omega-Terms. In E. W. Mayr and N. Portier, editors, STACS'14), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 374-385. Schloss Dagstuhl-Leibniz-Zentrumfuer Informatik, 2014.

M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, Mass., 1983.

S. W. Margolis, M. V. Sapir, and P. Weil. Closed subgroups in pro-V topologies and the extension problem for inverse automata. Int. J. Algebra Comput., 11:405-446, 2001.

J. P. McCammond. Normal forms for free aperiodic semigroups. Int. J. Algebra Comput., 11:581-625, 2001.

A. Moura. The word problem for [omega]-terms over DA. Theor. Comp. Sci., pages 6556-6569, 2011.

J. Pin. Topologies for the free monoid. J. Algebra, 137(2):297-337, 1991.

J.-E. Pin and Ch. Reutenauer. A conjecture on the Hall topology for the free group. Bull. London Math. Soc., 23:356-362, 1991.

T. Place and M. Zeitoun. Going higher in the first-order quantifier alternation hierarchy on words. In J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors, ICALP'14, volume 8573 of Lect. Notes Comp. Sci., pages 342-353, 2014a.

T. Place and M. Zeitoun. Separating regular languages with first-order logic. In CSL-LICS'14, pages 75:1-75:10, 2014b.

T. Place and M. Zeitoun. Separation and the Successor Relation. In E. W. Mayr and N. Ollinger, editors, STACS'15), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 662-675. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2015.

T. Place and M. Zeitoun. Separating regular languages with first-order logic. Logical Methods in Computer Science, 12(5):1-30, 2016.

J. Rhodes and B. Steinberg. The q-theory of finite semigroups. Springer Monographs in Mathematics. Springer, 2009.

L. Ribes and P. A. Zalesskii. On the profinite topology on a free group. Bull. London Math. Soc., 25: 37-43, 1993.

B. Steinberg. A delay theorem for pointlikes. Semigroup Forum, 63:281-304, 2001.

B. Steinberg. A combinatorial property of ideals in free profinite monoids. J. Pure Appl. Algebra, 214: 1693-1695, 2010.

H. Straubing. Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra, 15:319-327, 1979.

J. Almeida (1*)

J. C. Costa (2[dagger])

M. Zeitoun (3[double dagger])

(1) Centro de Matematica e Departamento de Matematica, Faculdade de Ciencias, Universidade do Porto, Portugal

(2) Centro de Matematica e Departamento de Matematica e Aplicacoes, Universidade do Minho, Portugal

(3) Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France

received 4th June 2015, accepted 2ndFeb. 2016.

(*) Work partially supported by CMUP (UID/MAT/ 00144/2013), which is funded by FCT (Portugal) with national (MCTES) and European structural funds (FEDER), under the partnership agreement PT2020.

([dagger]) Work supported, in part, by the European Regional Development Fund, through the program COMPETE, and by the Portuguese Government through FCT, under the project PEst-OE/MAT/UI0013/2014.

([double dagger]) Work carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of ANR 2010 BLAN 0202 01 FREC and of the "Investments for the future" Programme IdEx Bordeaux--CPU (ANR-10-IDEX-03-02).

(i) More precisely and technically, reducibility for 2-pointlike sets.
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:Almeida, J.; Costa, J.C.; Zeitoun, M.
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Nov 1, 2016
Words:13654
Previous Article:On the number of vertices of each rank in k-phylogenetic trees.
Next Article:Open k-monopolies in graphs: complexity and related concepts.
Topics:

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