{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:15Z","timestamp":1759638135395},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p> The quotient complexity of a regular language L, which is the same as its state complexity, is the number of left quotients of L. An atom of a non-empty regular language L with n quotients is a non-empty intersection of the n quotients, which can be uncomplemented or complemented. An NFA is atomic if the right language of every state is a union of atoms. We characterize all reduced atomic NFAs of a given language, i.e., those NFAs that have no equivalent states. We prove that, for any language L with quotient complexity n, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2<jats:sup>n<\/jats:sup> \u2212 1 if r = 0 or r = n; for 1 \u2264 r \u2264 n \u2212 1 the bound is[Formula: see text] For each n \u2265 2, we exhibit a language with 2<jats:sup>n<\/jats:sup> atoms which meet these bounds. <\/jats:p>","DOI":"10.1142\/s0129054113400285","type":"journal-article","created":{"date-parts":[[2014,2,27]],"date-time":"2014-02-27T02:16:43Z","timestamp":1393467403000},"page":"1009-1027","source":"Crossref","is-referenced-by-count":10,"title":["COMPLEXITY OF ATOMS OF REGULAR LANGUAGES"],"prefix":"10.1142","volume":"24","author":[{"given":"JANUSZ","family":"BRZOZOWSKI","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HELLIS","family":"TAMM","sequence":"additional","affiliation":[{"name":"Institute of Cybernetics, Tallinn University of Technology, Akadeemia tee 21, 12618 Tallinn, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,2,26]]},"reference":[{"issue":"1","key":"p_2","first-page":"71","volume":"15","author":"Brzozowski J.","year":"2010","journal-title":"J. Autom. Lang. Comb."},{"key":"p_4","first-page":"105","volume":"6795","author":"Brzozowski J.","year":"2011","journal-title":"G. Mauri and A. Leporati LNCS"},{"key":"p_6","first-page":"117","volume":"6795","author":"Brzozowski J.","year":"2011","journal-title":"G. Mauri and A. Leporati LNCS"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.032"},{"key":"p_9","first-page":"41","volume":"1","author":"Yu S.","year":"1997","journal-title":"Rozenberg and A. Salomaa"},{"key":"p_10","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"J. Autom. Lang. Comb."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T14:59:50Z","timestamp":1565103590000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":6,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2014,2,26]]},"published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1142\/S0129054113400285"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400285","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]}}}