UWSpace will be migrating to a new version of its software from July 29th to August 1st. UWSpace will be offline for all UW community members during this time.

Show simple item record

dc.contributor.authorLiu, Bo Yang Victor
dc.contributor.authorDavies, Sylvie
dc.contributor.authorBrzozowski, Janusz
dc.date.accessioned2017-11-13 22:52:27 (GMT)
dc.date.available2017-11-13 22:52:27 (GMT)
dc.description.abstractA right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$, $L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) of right, left, and two-sided regular ideals, where $L_n$ has quotient complexity (state complexity) $n$, such that $L_n$ is most complex in its class under the following measures of complexity: the size of the syntactic semigroup, the quotient complexities of the left quotients of $L_n$, the number of atoms (intersections of complemented and uncomplemented left quotients), the quotient complexities of the atoms, and the quotient complexities of reversal, star, product (concatenation), and all binary boolean operations. In that sense, these ideals are "most complex" languages in their classes, or "universal witnesses" to the complexity of the various operations.en
dc.description.sponsorshipNatural Sciences and Engineering Research Council of Canada [OGP0000871]en
dc.publisherDiscrete Mathematics and Theoretical Computer Scienceen
dc.rightsAttribution 4.0 International*
dc.subjectbasic operationsen
dc.subjectmost complexen
dc.subjectregular languageen
dc.subjectstate complexityen
dc.subjectsyntactic semigroupen
dc.subjectuniversal witnessen
dc.titleMost Complex Regular Ideal Languagesen
dcterms.bibliographicCitationLiu, B. Y. V., Davies, S., & Brzozowski, J. (2016). Most Complex Regular Ideal Languages. Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 3. Retrieved from http://dmtcs.episciences.org/2167/pdfen
uws.contributor.affiliation1Faculty of Mathematicsen
uws.contributor.affiliation2David R. Cheriton School of Computer Scienceen

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's license is described as Attribution 4.0 International


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages