{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:27:34Z","timestamp":1743085654253,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319946306"},{"type":"electronic","value":"9783319946313"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94631-3_4","type":"book-chapter","created":{"date-parts":[[2018,7,10]],"date-time":"2018-07-10T06:09:52Z","timestamp":1531202992000},"page":"37-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Most Complex Deterministic Union-Free Regular Languages"],"prefix":"10.1007","author":[{"given":"Janusz A.","family":"Brzozowski","sequence":"first","affiliation":[]},{"given":"Sylvie","family":"Davies","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-00982-2_7","volume-title":"Language and Automata Theory and Applications","author":"S Afonin","year":"2009","unstructured":"Afonin, S., Golomazov, D.: Minimal union-free decompositions of regular languages. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 83\u201392. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00982-2_7"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-43951-7_1","volume-title":"Automata, Languages, and Programming","author":"J Bell","year":"2014","unstructured":"Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of boolean operations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 1\u201312. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_1"},{"key":"4_CR3","unstructured":"Brzozowski, J.A.: Regular expression techniques for sequential circuits. Ph.D. thesis, Princeton University, Princeton, NJ (1962). http:\/\/maveric.uwaterloo.ca\/~brzozo\/publication.html"},{"issue":"6","key":"4_CR4","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1142\/S0129054113400133","volume":"24","author":"JA Brzozowski","year":"2013","unstructured":"Brzozowski, J.A.: In search of the most complex regular languages. Int. J. Found. Comput. Sci. 24(6), 691\u2013708 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.14232\/actacyb.22.2.2015.4","volume":"22","author":"JA Brzozowski","year":"2015","unstructured":"Brzozowski, J.A., Davies, S.: Quotient complexities of atoms of regular ideal languages. Acta Cybern. 22, 293\u2013311 (2015)","journal-title":"Acta Cybern."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Davies, S., Liu, B.Y.V.: Most complex regular ideal languages. Discrete Math. Theor. Comput. Sci. 18(3) (2016). Paper #15","DOI":"10.46298\/dmtcs.1343"},{"key":"4_CR7","unstructured":"Brzozowski, J.A., Sinnamon, C.: Unrestricted state complexity of binary operations on regular and ideal languages (2016). http:\/\/arxiv.org\/abs\/1609.04439. Accessed 2017"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.14232\/actacyb.23.1.2017.3","volume":"23","author":"JA Brzozowski","year":"2017","unstructured":"Brzozowski, J.A., Sinnamon, C.: Complexity of right-ideal, prefix-closed, and prefix-free regular languages. Acta Cybern. 23(1), 9\u201341 (2017)","journal-title":"Acta Cybern."},{"issue":"1\u20133","key":"4_CR9","first-page":"29","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)","journal-title":"J. Autom. Lang. Comb."},{"issue":"7","key":"4_CR10","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1142\/S0129054115400067","volume":"26","author":"JA Brzozowski","year":"2015","unstructured":"Brzozowski, J.A., Szyku\u0142a, M.: Large aperiodic semigroups. Int. J. Found. Comput. Sci. 26(7), 913\u2013931 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"7","key":"4_CR11","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1142\/S0129054113400285","volume":"24","author":"JA Brzozowski","year":"2013","unstructured":"Brzozowski, J.A., Tamm, H.: Complexity of atoms of regular languages. Int. J. Found. Comput. Sci. 24(7), 1009\u20131027 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.016","volume":"539","author":"JA Brzozowski","year":"2014","unstructured":"Brzozowski, J.A., Tamm, H.: Theory of \u00e1tomata. Theor. Comput. Sci. 539, 13\u201327 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1006\/inco.2000.2889","volume":"164","author":"S Crvenkovi\u0107","year":"2001","unstructured":"Crvenkovi\u0107, S., Dolinka, I., \u00c9sik, Z.: On equations for union-free regular languages. Inf. Comput. 164, 152\u2013172 (2001)","journal-title":"Inf. Comput."},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-319-94631-3_7","volume-title":"Descriptional Complexity of Formal Systems","author":"S Davies","year":"2018","unstructured":"Davies, S.: A new technique for reachability of states in concatenation automata. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10316, pp. 75\u201387. Springer, Cham (2018). Earlier version at https:\/\/arxiv.org\/abs\/1710.05061"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/9789813148208_0003","volume-title":"The Role of Theory in Computer Science","author":"M Holzer","year":"2017","unstructured":"Holzer, M., Kutrib, M.: Structure and complexity of some subregular language families. In: Konstantinidis, S., Moreira, N., Reis, R., Shallit, J. (eds.) The Role of Theory in Computer Science, pp. 59\u201382. World Scientific, Singapore (2017)"},{"issue":"5","key":"4_CR16","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.ipl.2016.01.003","volume":"116","author":"S Iv\u00e1n","year":"2016","unstructured":"Iv\u00e1n, S.: Complexity of atoms, combinatorially. Inf. Process. Lett. 116(5), 356\u2013360 (2016)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"4_CR17","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1142\/S0129054111008933","volume":"22","author":"G Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G., Masopust, T.: Complexity in union-free regular languages. Int. J. Found. Comput. Sci. 22(7), 1639\u20131653 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-33475-7_13","volume-title":"Theoretical Computer Science","author":"G Jir\u00e1skov\u00e1","year":"2012","unstructured":"Jir\u00e1skov\u00e1, G., Nagy, B.: On union-free and deterministic union-free languages. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol. 7604, pp. 179\u2013192. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33475-7_13"},{"issue":"Suppl. C","key":"4_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2016.08.014","volume":"679","author":"M Kutrib","year":"2017","unstructured":"Kutrib, M., Wendlandt, M.: Concatenation-free languages. Theor. Comput. Sci. 679(Suppl. C), 83\u201394 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR20","first-page":"1266","volume":"194","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266\u20131268 (1970). (in Russian). English translation: Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR21","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. The MIT Press, Cambridge (1971)"},{"issue":"1\u20132","key":"4_CR22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.5486\/PMD.2006.3303","volume":"68","author":"B Nagy","year":"2006","unstructured":"Nagy, B.: Union-free regular languages and 1-cycle-free-path-automata. Publ. Math. Debr. 68(1\u20132), 183\u2013197 (2006)","journal-title":"Publ. Math. Debr."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Nagy, B.: On union complexity of regular languages. In: CINTI 2010, pp. 177\u2013182. IEEE (2010)","DOI":"10.1109\/CINTI.2010.5672252"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-642-59136-5_10","volume-title":"Handbook of Formal Languages, vol. 1: Word, Language, Grammar","author":"JE Pin","year":"1997","unstructured":"Pin, J.E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1: Word, Language, Grammar, pp. 679\u2013746. Springer, New York (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_10"},{"key":"4_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. Theor. Comput. Sci. 320, 315\u2013329 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.: On finite monoids having only trivial subgroups. Inf. Control 8, 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"4_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, 315\u2013328 (1994)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94631-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:15:53Z","timestamp":1710324953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94631-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319946306","9783319946313"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94631-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"11 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Halifax, NS","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cs.smu.ca\/~dcfs2018\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}