{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T03:53:41Z","timestamp":1768449221518,"version":"3.49.0"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,12]]},"abstract":"<jats:p> We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operations \u2013 concatenation, iteration, \u03bb-free iteration \u2013 and the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. Otherwise tight bounds in the order of magnitude are shown. <\/jats:p>","DOI":"10.1142\/s0129054103002199","type":"journal-article","created":{"date-parts":[[2003,12,19]],"date-time":"2003-12-19T05:51:21Z","timestamp":1071813081000},"page":"1087-1102","source":"Crossref","is-referenced-by-count":115,"title":["NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES"],"prefix":"10.1142","volume":"14","author":[{"given":"MARKUS","family":"HOLZER","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik,  Technische Universit\u00e4t M\u00fcnchen, Boltzmannstra\u00dfe 3,  D-85748 Garching bei M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTIN","family":"KUTRIB","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik,  Universit\u00e4t Giessen, Arndtstra\u00dfe 2,  D-35392 Giessen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90160-U"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01371727"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00292-9"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"key":"rf8","volume-title":"Introduction to Automata Theory, Language, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0222067"},{"key":"rf11","first-page":"92","volume":"3","author":"Landau E.","journal-title":"Archiv der Math., und Phys."},{"key":"rf12","volume-title":"Handbuch der Lehre von der Verteilung der Primzahlen","author":"Landau E.","year":"1909"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"rf14","first-page":"287","volume":"5","author":"Mereghetti C.","journal-title":"J. Aut. Lang., and Comb."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979935431X"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"rf20","first-page":"177","volume":"2","author":"Salomaa K.","journal-title":"J. Aut., Lang., and Comb."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90034-3"},{"key":"rf24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4064\/aa-37-1-321-331","volume":"37","author":"Szalay M.","journal-title":"Acta Arithm."},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"rf26","first-page":"221","volume":"6","author":"Yu S.","journal-title":"J. Aut. Lang. and Comb."},{"key":"rf27","first-page":"142","volume":"76","author":"Yu S.","journal-title":"Bull. EATCS"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103002199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:25:58Z","timestamp":1565191558000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103002199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":20,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,12]]}},"alternative-id":["10.1142\/S0129054103002199"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103002199","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}