dc.contributor.author | Brzozowski, Janusz | |
dc.contributor.author | Szykuła, Marek | |
dc.date.accessioned | 2017-09-29 14:03:06 (GMT) | |
dc.date.available | 2017-09-29 14:03:06 (GMT) | |
dc.date.issued | 2015-11-01 | |
dc.identifier.uri | http://dx.doi.org/10.1142/S0129054115400067 | |
dc.identifier.uri | http://hdl.handle.net/10012/12507 | |
dc.description | 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/ | en |
dc.description.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. | en |
dc.description.sponsorship | Natural Sciences and Engineering Research Council of Canada [OGP000087] | en |
dc.description.sponsorship | Polish MNiSZW [IP2012 052272] | en |
dc.language.iso | en | en |
dc.publisher | World Scientific Publishing | en |
dc.subject | Aperiodic | en |
dc.subject | monotonic | en |
dc.subject | semiconstant | en |
dc.subject | transition semigroup | en |
dc.subject | star-free language | en |
dc.subject | syntactic complexity | en |
dc.subject | unitary. | en |
dc.title | Large Aperiodic Semigroups | en |
dc.type | Conference Paper | en |
dcterms.bibliographicCitation | Brzozowski, J., & Szykuła, M. (2015). Large Aperiodic Semigroups. International Journal of Foundations of Computer Science, 26(07), 913–931. https://doi.org/10.1142/S0129054115400067 | en |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.contributor.affiliation2 | David R. Cheriton School of Computer Science | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Reviewed | en |
uws.scholarLevel | Faculty | en |