Large Aperiodic Semigroups
Abstract
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.
Collections
Cite this version of the work
Janusz Brzozowski, Marek Szykuła
(2015).
Large Aperiodic Semigroups. UWSpace.
http://hdl.handle.net/10012/12507
Other formats