{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:18:16Z","timestamp":1754194696388},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,3,26]],"date-time":"2018-03-26T00:00:00Z","timestamp":1522022400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["OGP0000871"],"award-info":[{"award-number":["OGP0000871"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-018-9859-0","type":"journal-article","created":{"date-parts":[[2018,3,26]],"date-time":"2018-03-26T04:34:09Z","timestamp":1522038849000},"page":"1952-2005","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Primitivity, Uniform Minimality, and State Complexity of Boolean Operations"],"prefix":"10.1007","volume":"62","author":[{"given":"Sylvie","family":"Davies","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,26]]},"reference":[{"issue":"02","key":"9859_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1142\/S0129054116400037","volume":"27","author":"J Almeida","year":"2016","unstructured":"Almeida, J., Rodaro, E.: Semisimple synchronizing automata and the Wedderburn-Artin theory. Int. J. Found. Comput. Sc. 27(02), 127\u2013145 (2016). https:\/\/doi.org\/10.1142\/S0129054116400037","journal-title":"Int. J. Found. Comput. Sc."},{"key":"9859_CR2","unstructured":"Ara\u00fajo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: synchronization and its friends. arXiv: 1511.03184 (2015)"},{"key":"9859_CR3","doi-asserted-by":"publisher","unstructured":"Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of boolean operations. In: Esparza, J., et al. (eds.) ICALP 2014, LNCS, vol. 8573, pp 1\u201312. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_1","DOI":"10.1007\/978-3-662-43951-7_1"},{"issue":"3\u20134","key":"9859_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user language. J. Symbolic Comput. 24(3\u20134), 235\u2013265 (1997). https:\/\/doi.org\/10.1006\/jsco.1996.0125","journal-title":"J. Symbolic Comput."},{"issue":"1\/2","key":"9859_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.4204\/EPTCS.3.2","volume":"15","author":"J Brzozowski","year":"2010","unstructured":"Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1\/2), 71\u201389 (2010). https:\/\/doi.org\/10.4204\/EPTCS.3.2","journal-title":"J. Autom. Lang. Comb."},{"issue":"06","key":"9859_CR6","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1142\/S0129054113400133","volume":"24","author":"J Brzozowski","year":"2013","unstructured":"Brzozowski, J.: In search of most complex regular languages. Int. J. Found. Comput. Sci. 24(06), 691\u2013708 (2013). https:\/\/doi.org\/10.1142\/S0129054113400133","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9859_CR7","doi-asserted-by":"publisher","unstructured":"Brzozowski, J.: Unrestricted state complexity of binary operations on regular languages. In: C\u00e2mpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016, LNCS, vol. 9777, pp 60\u201372. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-41114-9_5","DOI":"10.1007\/978-3-319-41114-9_5"},{"key":"9859_CR8","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2012.10.055","volume":"470","author":"J Brzozowski","year":"2013","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B.: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 36\u201352 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.10.055","journal-title":"Theoret. Comput. Sci."},{"issue":"06","key":"9859_CR9","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1142\/S0129054112400515","volume":"23","author":"J Brzozowski","year":"2012","unstructured":"Brzozowski, J., Liu, B.: Quotient complexity of star-free languages. Int. J. Found. Comput. Sci. 23(06), 1261\u20131276 (2012). https:\/\/doi.org\/10.1142\/S0129054112400515","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9859_CR10","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Davies, S., Liu, B.Y.V.: Most complex regular ideal languages. Discret. Math. Theoret. Comput. Sci. 18(3). Paper #15. https:\/\/dmtcs.episciences.org\/volume\/view\/id\/184 (2016)","DOI":"10.46298\/dmtcs.1343"},{"issue":"1\u20133","key":"9859_CR11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.25596\/jalc-2017-029","volume":"22","author":"JA Brzozowski","year":"2017","unstructured":"Brzozowski, J.A., Sinnamon, C.: Unrestricted state complexity of binary operations on regular and ideal languages. J. Autom. Lang. Comb. 22(1\u20133), 29\u201359 (2017). https:\/\/doi.org\/10.25596\/jalc-2017-029","journal-title":"J. Autom. Lang. Comb."},{"issue":"1","key":"9859_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/blms\/13.1.1","volume":"13","author":"PJ Cameron","year":"1981","unstructured":"Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. London Math. Soc. 13(1), 1\u201322 (1981). https:\/\/doi.org\/10.1112\/blms\/13.1.1","journal-title":"Bull. London Math. Soc."},{"key":"9859_CR13","unstructured":"Delgado, M., Linton, S., Morais, J.: Automata \u2013 a GAP package, Version 1.13. http:\/\/cmup.fc.up.pt\/cmup\/mdelgado\/automata\/ (2011)"},{"key":"9859_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0731-3","volume-title":"Permutation groups","author":"JD Dixon","year":"1996","unstructured":"Dixon, J.D., Mortimer, B.: Permutation groups. Springer, Berlin (1996). https:\/\/doi.org\/10.1007\/978-1-4612-0731-3 https:\/\/doi.org\/10.1007\/978-1-4612-0731-3"},{"key":"9859_CR15","volume-title":"Abstract Algebra","author":"D Dummit","year":"2004","unstructured":"Dummit, D., Foote, R.: Abstract Algebra. Wiley, NY (2004)"},{"issue":"35","key":"9859_CR16","doi-asserted-by":"publisher","first-page":"3272","DOI":"10.1016\/j.tcs.2009.03.026","volume":"410","author":"Z \u00c9sik","year":"2009","unstructured":"\u00c9sik, Z., Gao, Y., Liu, G., Yu, S.: Estimation of state complexity of combined operations. Theoret. Comput. Sci. 410(35), 3272\u20133280 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.03.026","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"9859_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.25596\/jalc-2016-251","volume":"21","author":"Y Gao","year":"2016","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Autom. Lang. Comb. 21(4), 251\u2013310 (2016). https:\/\/doi.org\/10.25596\/jalc-2016-251","journal-title":"J. Autom. Lang. Comb."},{"issue":"05","key":"9859_CR18","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1142\/S0129054112400461","volume":"23","author":"Y Gao","year":"2012","unstructured":"Gao, Y., Yu, S.: State complexity and approximation. Int. J. Found. Comput. Sci. 23(05), 1085\u20131098 (2012). https:\/\/doi.org\/10.1142\/S0129054112400461","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9859_CR19","unstructured":"The GAP Group: GAP \u2013 Groups, Algorithms, and Programming, Version 4.8.6 (2016). http:\/\/www.gap-system.org"},{"key":"9859_CR20","doi-asserted-by":"publisher","unstructured":"Kiraz, G.A.: Compressed storage of sparse finite-state transducers. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999, LNCS, vol. 2214, pp 109\u2013121. Springer (2001). https:\/\/doi.org\/10.1007\/3-540-45526-4_11","DOI":"10.1007\/3-540-45526-4_11"},{"key":"9859_CR21","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266\u20131268 (Russian) (1970). English translation: Soviet Math. Dokl. 11 (1970) 1373\u20131375"},{"key":"9859_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2012.03.049","volume":"440\u2013441","author":"A Restivo","year":"2012","unstructured":"Restivo, A., Vaglica, R.: Extremal minimality conditions on automata. Theor. Comput. Sci. 440\u2013441, 73\u201384 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.049","journal-title":"Theor. Comput. Sci."},{"key":"9859_CR23","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.tcs.2011.12.049","volume":"429","author":"A Restivo","year":"2012","unstructured":"Restivo, A., Vaglica, R.: A graph theoretic approach to automata minimality. Theoret. Comput. Sci. 429, 282\u2013291 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2011.12.049","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"9859_CR24","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.tcs.2007.04.015","volume":"383","author":"A Salomaa","year":"2007","unstructured":"Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci. 383(2), 140\u2013152 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.04.015","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"9859_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2004.02.032","volume":"320","author":"A Salomaa","year":"2004","unstructured":"Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320(2), 315\u2013329 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.02.032","journal-title":"Theoret. Comput. Sci."},{"key":"9859_CR26","doi-asserted-by":"crossref","unstructured":"Steinberg, B.: A theory of transformation monoids: combinatorics and representation theory. arXiv: https:\/\/arxiv.org\/abs\/1004.2982 (2010)","DOI":"10.37236\/436"},{"issue":"2","key":"9859_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315\u2013328 (1994). https:\/\/doi.org\/10.1016\/0304-3975(92)00011-F","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9859-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9859-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9859-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T23:56:14Z","timestamp":1660694174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9859-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,26]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9859"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9859-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,26]]},"assertion":[{"value":"26 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}