{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:46:29Z","timestamp":1772372789317,"version":"3.50.1"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> We examine the accepting state complexity, i.e., the minimal number of accepting states of deterministic finite automata for languages resulting from unary and binary operations on languages with accepting state complexity given as a parameter. This is a continuation of the work of [J. Dassow: On the number of accepting states of finite automata, J. Autom., Lang. Comb., 21, 2016]. We solve most of the open problems mentioned thereof. In particular, we consider the operations of intersection, symmetric difference, right and left quotients, reversal, and permutation (on finite languages), where we obtain precise ranges of accepting state complexities. We also consider symmetric difference on unary finite languages where we obtain a non-contiguous range of accepting state complexities. <\/jats:p>","DOI":"10.1142\/s0129054120420083","type":"journal-article","created":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T16:57:33Z","timestamp":1609347453000},"page":"1159-1177","source":"Crossref","is-referenced-by-count":3,"title":["The Ranges of Accepting State Complexities of Languages Resulting from Some Operations"],"prefix":"10.1142","volume":"31","author":[{"given":"Michal","family":"Hospod\u00e1r","sequence":"first","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, Ko\u0161ice, 040 01, Slovakia"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2020,12,30]]},"reference":[{"key":"S0129054120420083BIB001","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2017.03.007","volume":"682","author":"Cho D.-J.","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420083BIB003","first-page":"55","volume":"21","author":"Dassow J.","year":"2016","journal-title":"J. Autom. Lang. Comb."},{"key":"S0129054120420083BIB004","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-319-60252-3_3","volume-title":"DCFS 2017","volume":"10316","author":"Dassow J.","year":"2017"},{"issue":"1","key":"S0129054120420083BIB005","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1080\/00207169008803893","volume":"35","author":"Fellah A.","year":"1990","journal-title":"Int. J. Comput. Math."},{"issue":"11","key":"S0129054120420083BIB006","doi-asserted-by":"crossref","first-page":"1652","DOI":"10.1016\/j.ic.2007.07.001","volume":"205","author":"Geffert V.","year":"2007","journal-title":"Inform. Comput."},{"key":"S0129054120420083BIB007","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"S0129054120420083BIB008","first-page":"170","volume-title":"DCFS 2005","author":"Hricko M.","year":"2005"},{"issue":"1","key":"S0129054120420083BIB009","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/S0304-3975(00)00029-3","volume":"237","author":"Iwama K.","year":"2000","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420083BIB010","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/3-540-44612-5_39","volume-title":"MFCS 2000","volume":"1893","author":"Iwama K.","year":"2000"},{"issue":"2","key":"S0129054120420083BIB011","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1142\/S0129054111008076","volume":"22","author":"Jir\u00e1skov\u00e1 G.","year":"2011","journal-title":"Int. J. Found. Comput. Sci."},{"key":"S0129054120420083BIB012","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/978-3-319-08846-4_17","volume-title":"CIAA 2014","volume":"8587","author":"Jir\u00e1skov\u00e1 G.","year":"2014"},{"key":"S0129054120420083BIB013","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2012.05.008","volume":"449","author":"Jir\u00e1skov\u00e1 G.","year":"2012","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"S0129054120420083BIB014","first-page":"123","volume":"22","author":"Jir\u00e1skov\u00e1 G.","year":"2017","journal-title":"J. Autom. Lang. Comb."},{"issue":"3","key":"S0129054120420083BIB015","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"Leiss E.","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420083BIB016","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/978-3-642-39310-5_25","volume-title":"DCFS 2013","volume":"8031","author":"\u0160ebej J.","year":"2013"},{"key":"S0129054120420083BIB017","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages \u2014 Vol. I","author":"Yu S.","year":"1997"},{"issue":"3","key":"S0129054120420083BIB018","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/126537.126543","volume":"22","author":"Yu S.","year":"1991","journal-title":"SIGACT News"},{"issue":"2","key":"S0129054120420083BIB019","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"Yu S.","year":"1994","journal-title":"Theoret. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120420083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:33:22Z","timestamp":1611200002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120420083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":18,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S0129054120420083"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120420083","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}