{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:07:38Z","timestamp":1778677658110,"version":"3.51.4"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>We investigate the state complexity of concatenation and the nondeterministic state complexity of complementation of regular languages. We show that the upper bounds on the state complexity of concatenation are also tight in the case that the first automaton has more than one accepting state. In the case of nondeterministic state complexity of complementation, we show that the entire range of complexities, up to the known upper bound can be produced.<\/jats:p>","DOI":"10.1142\/s0129054105003133","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"511-529","source":"Crossref","is-referenced-by-count":55,"title":["STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION"],"prefix":"10.1142","volume":"16","author":[{"given":"JOZEF","family":"JIR\u00c1SEK","sequence":"first","affiliation":[{"name":"Institute of Computer Science, P.J. \u0160af\u00e1rik University, Jesenn\u00e1 5, 040 01 Ko\u0161ice, Slovakia"}]},{"given":"GALINA","family":"JIR\u00c1SKOV\u00c1","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"given":"ALEXANDER","family":"SZABARI","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, P. J. \u0160af\u00e1rik University, Jesenn\u00e1 5, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90160-U"},{"key":"rf4","doi-asserted-by":"crossref","unstructured":"C.\u00a0C\u00e2mpeanu, Proc. 4th International Workshop on Implementing Automata (WIA '99), LNCS 2214, eds. O.\u00a0Boldt and H.\u00a0J\u00fcrgensen (Springer-Verlag, Heidelberg, 2001)\u00a0pp. 60\u201370.","DOI":"10.1007\/3-540-45526-4_6"},{"key":"rf5","first-page":"303","volume":"7","author":"C\u00e2mpeanu C.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"key":"rf7","first-page":"455","volume":"7","author":"Domaratzki M.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"rf9","first-page":"453","volume":"6","author":"Holzer M.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44977-9_14"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45005-X_14"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03442-2"},{"key":"rf14","first-page":"519","volume":"7","author":"Hromkovi\u010d J.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3069"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1201\/9780203009642.ch16"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"rf19","first-page":"321","volume":"9","author":"Lupanov O. B.","journal-title":"Problemy Kibernetiki"},{"key":"rf21","first-page":"1211","volume":"20","author":"Moore F. R.","journal-title":"IEEE Trans. Comput."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44674-5_21"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"rf26","volume-title":"Introduction to the theory of computation","author":"Sipser M.","year":"1997"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"rf29","first-page":"270","volume":"72","author":"Yu S.","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"rf30","first-page":"270","volume":"76","author":"Yu S.","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"rf31","first-page":"221","volume":"6","author":"Yu S.","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\/S0129054105003133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T17:54:47Z","timestamp":1683136487000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":28,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0129054105003133"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003133","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}