{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:23:18Z","timestamp":1770963798906,"version":"3.50.1"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"name":"Operational Programme Integrated Infrastructure","award":["313011BWH2"],"award-info":[{"award-number":["313011BWH2"]}]},{"name":"Slovak Grant Agency for Science","award":["contract 2\/0096\/23"],"award-info":[{"award-number":["contract 2\/0096\/23"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>We study the state complexity of regular operations on the classes of combinational, singleton, finitely generated left ideal, symmetric definite, star, comet, two-sided comet, ordered, star-free, and power-separating languages. For the operations of union, intersection, concatenation, cut, positive closure, star, and reversal, we get tight upper bounds for all considered classes. The complexity of all operations on combinational languages is given by a constant function, and on singleton languages by a linear function. In most of the remaining cases, the state complexity of considered operations is either the same as in the regular case, or just slightly smaller. On the other hand, the complexity of concatenation on finitely generated left ideals and of star and positive closure on symmetric definite and star languages is much smaller than in the regular case. All our witnesses are described over a small fixed alphabet, mostly a binary one, except for witnesses for reversal on finitely generated left ideals and ordered languages.<\/jats:p>","DOI":"10.1142\/s0129054125410060","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T05:07:36Z","timestamp":1747717656000},"page":"137-165","source":"Crossref","is-referenced-by-count":1,"title":["Operational Complexity in Subregular Classes"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-6904-5054","authenticated-orcid":false,"given":"Michaela","family":"Bobeni\u010dov\u00e1","sequence":"first","affiliation":[{"name":"Institute of Computer Science, P.J.\u00a0\u0160af\u00e1rik University, Jesenn\u00e1 5, 040 01 Ko\u0161ice, Slovakia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1752-544X","authenticated-orcid":false,"given":"Michal","family":"Hospod\u00e1r","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9817-8197","authenticated-orcid":false,"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"S0129054125410060BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38771-5_8"},{"key":"S0129054125410060BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.019"},{"key":"S0129054125410060BIB003","doi-asserted-by":"publisher","DOI":"10.14232\/actacyb.21.4.2014.1"},{"key":"S0129054125410060BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.055"},{"key":"S0129054125410060BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9515-7"},{"key":"S0129054125410060BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400515"},{"key":"S0129054125410060BIB007","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"WIA 1999","volume":"2214","author":"C\u00e2mpeanu C.","year":"1999"},{"key":"S0129054125410060BIB008","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1577"},{"key":"S0129054125410060BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"S0129054125410060BIB010","first-page":"99","volume-title":"Automata, Formal Languages, and Related Topics","author":"Han Y.-S.","year":"2009"},{"key":"S0129054125410060BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-13435-8_14"},{"key":"S0129054125410060BIB012","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054125410060BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114050"},{"key":"S0129054125410060BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114075"},{"key":"S0129054125410060BIB015","author":"Iv\u00e1n S.","year":"2013","journal-title":"CoRR"},{"key":"S0129054125410060BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.008"},{"key":"S0129054125410060BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38771-5_26"},{"key":"S0129054125410060BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"S0129054125410060BIB019","first-page":"1373","volume":"11","author":"Maslov A. N.","year":"1970","journal-title":"Soviet Math. Doklady"},{"key":"S0129054125410060BIB020","unstructured":"V. Olej\u00e1r and A. Szabari, Closure properties of subregular languages under operations,\n                      Int. J. Found. Comput. Sci.\n                      https:\/\/doi.org\/10.1142\/S0129054123450016 (online ready). Preliminary version in:\n                      MCU 2022\n                      , eds. J. Durand-Lose and G. Vaszil, Lect. Notes Comput. Sci., Vol. 13419 (Springer, 2022), pp. 126\u2013142."},{"key":"S0129054125410060BIB021","doi-asserted-by":"publisher","DOI":"10.1145\/321281.321292"},{"key":"S0129054125410060BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"S0129054125410060BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"S0129054125410060BIB024","first-page":"9","volume":"5","author":"Shyr H.-J.","year":"1974","journal-title":"Tamkang J. Math."},{"key":"S0129054125410060BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/BF01761710"},{"key":"S0129054125410060BIB026","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2012"},{"key":"S0129054125410060BIB027","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\/S0129054125410060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:00Z","timestamp":1770961020000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,20]]},"references-count":27,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410060"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410060","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,20]]}}}