Large Aperiodic Semigroups

Electronic version of an article published as: International Journal of Foundations of Computer Science, 26(07), 2015, 913–931. http://dx.doi.org/10.1142/S0129054115400067 © World Scientific Publishing Company http://www.worldscientific.com/We search for the largest syntactic semigroups of star-free languages having n left quotients; equivalently, we look for the largest transition semigroups of aperiodic finite automata with n states. We first introduce unitary semigroups generated by transformations that change only one state. In particular, we study unitary-complete semigroups which have a special structure, and show that each maximal unitary semigroup is unitary-complete. For n >= 4 we exhibit a unitary-complete semigroup that is larger than any aperiodic semigroup known to date. We then present even larger aperiodic semigroups, generated by transformations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. 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.Natural Sciences and Engineering Research Council of Canada [OGP000087]Polish MNiSZW [IP2012 052272