Closures of regular languages for profinite topologies

Abstract

The Pin-Reutenauer algorithm gives a method, that can be viewed as a descriptive procedure, to compute the closure in the free group of a regular language with respect to the Hall topology. A similar descriptive procedure is shown to hold for the pseudovariety A of aperiodic semigroups, where the closure is taken in the free aperiodic omega-semigroup. It is inherited by a subpseudovariety of a given pseudovariety if both of them enjoy the property of being full. The pseudovariety A, as well as some of its subpseudovarieties are shown to be full. The interest in such descriptions stems from the fact that, for each of the main pseudovarieties V in our examples, the closures of two regular languages are disjoint if and only if the languages can be separated by a language whose syntactic semigroup lies in V. In the cases of A and of the pseudovariety DA of semigroups in which all regular elements are idempotents, this is a new result.