Large Aperiodic Semigroups

Abstract. We search for the largest syntactic semigroup of a star-free language having n left quotients; equivalently, we look for the largest transition semigroup of an aperiodic finite automaton with n states. We first introduce unitary semigroups generated by transformations that change only one state. In particular, we study complete unitary semi-groups which have a special structure, and we show that each maximal unitary semigroup is complete. For n 4 there exists a complete unitary semigroup that is larger than any aperiodic semigroup known to date. We then present even larger aperiodic semigroups, generated by trans-formations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. In particular, we examine semiconstant tree semigroups which have a structure based on full binary trees. The semiconstant tree semigroups are at present the best candidates for largest aperiodic semigroups