Pointlike sets: the finest aperiodic cover of a finite semigroup

AbstractThe research in this paper is motivated by the open question: “Is the complexity of a finite semigroup S decidable?” Following the lead of the Presentation Lemma (Rhodes), we describe the finest cover on S that can be computed using an aperiodic semigroup and give an explicit relation. The central idea of the proof is that an aperiodic computation can be described by a new ‘blow-up operator’ Hω. The proof also relies on the Rhodes expansion of S and on Zeiger coding