{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:14Z","timestamp":1760202674320},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p> We examine the deterministic and nondeterministic state complexity of complements, stars, and reversals of regular languages. Our results are as follows: <\/jats:p><jats:p> (1) The nondeterministic state complexity of the complement of an n-state nfa language over a five-letter alphabet may reach each value from log n to 2<jats:sup>n<\/jats:sup>. <\/jats:p><jats:p> (2) The state complexity of the star (reversal) of an n-state dfa language over a growing alphabet may reach each value from 1 to [Formula: see text] (from log n to 2<jats:sup>n<\/jats:sup>, respectively). <\/jats:p><jats:p> (3) The nondeterministic state complexity of the star (reversal) of an n-state nfa binary language may reach each value from 1 to n + 1 (from n - 1 to n + 1, respectively). <\/jats:p><jats:p> We also obtain some partial results on the nondeterministic state complexity of complements of binary regular languages. As a bonus, we get an exponential number of values that are non-magic in the binary case. <\/jats:p>","DOI":"10.1142\/s0129054114500063","type":"journal-article","created":{"date-parts":[[2014,4,29]],"date-time":"2014-04-29T02:35:13Z","timestamp":1398738913000},"page":"101-124","source":"Crossref","is-referenced-by-count":5,"title":["THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES"],"prefix":"10.1142","volume":"25","author":[{"given":"GALINA","family":"JIR\u00c1SKOV\u00c1","sequence":"first","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2014,4,28]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90160-U"},{"key":"p_3","first-page":"35","volume":"83","author":"Dassow J.","year":"2008","journal-title":"Fundam. Inform."},{"key":"p_4","first-page":"139","volume":"12","author":"Geffert V.","year":"2007","journal-title":"J. Autom. Lang. Comb."},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.07.001"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"p_9","first-page":"519","volume":"7","author":"J.","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00029-3"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00891-5"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008076"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005851"},{"key":"p_19","first-page":"270","volume":"72","author":"Yu S.","year":"2000","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003455"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114500063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:46:20Z","timestamp":1565117180000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114500063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":17,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2014,4,28]]},"published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1142\/S0129054114500063"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114500063","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}