{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T17:21:37Z","timestamp":1694107297104},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"DOI":"10.13039\/501100006109","name":"VEGA","doi-asserted-by":"crossref","award":["2\/0084\/15"],"award-info":[{"award-number":["2\/0084\/15"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005357","name":"APVV","doi-asserted-by":"crossref","award":["15-0091"],"award-info":[{"award-number":["15-0091"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> We investigate the state complexity of the square operation on languages represented by deterministic, alternating, and Boolean automata. For each [Formula: see text] such that [Formula: see text], we describe a binary language accepted by an [Formula: see text]-state deterministic finite automaton with [Formula: see text] final states meeting the upper bound [Formula: see text] on the state complexity of its square. We show that in the case of [Formula: see text], the corresponding upper bound cannot be met. Using the binary deterministic witness for square with [Formula: see text] states where half of them are final, we get the tight upper bounds [Formula: see text] and [Formula: see text] on the complexity of the square operation on alternating and Boolean automata, respectively. <\/jats:p>","DOI":"10.1142\/s0129054119400318","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1117-1134","source":"Crossref","is-referenced-by-count":1,"title":["Square on Deterministic, Alternating, and Boolean Finite Automata"],"prefix":"10.1142","volume":"30","author":[{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"first","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"given":"Ivana","family":"Kraj\u0148\u00e1kov\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":[[2019,9,19]]},"reference":[{"key":"S0129054119400318BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90069-9"},{"key":"S0129054119400318BIB002","series-title":"LNCS","first-page":"136","volume-title":"CIAA 2014","volume":"8587","author":"\u010cevorov\u00e1 K.","year":"2014"},{"key":"S0129054119400318BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.025"},{"key":"S0129054119400318BIB004","doi-asserted-by":"publisher","DOI":"10.1080\/00207169008803893"},{"key":"S0129054119400318BIB005","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054119400318BIB006","first-page":"179","volume-title":"NCMA 2016","volume":"321","author":"Hospod\u00e1r M.","year":"2016"},{"key":"S0129054119400318BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30642-6_19"},{"key":"S0129054119400318BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"issue":"5","key":"S0129054119400318BIB009","first-page":"1373","volume":"11","author":"Maslov A. N.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"S0129054119400318BIB010","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"S0129054119400318BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.011"},{"key":"S0129054119400318BIB012","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2012"},{"key":"S0129054119400318BIB014","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\/S0129054119400318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:46Z","timestamp":1568876806000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":13,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400318"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400318","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}