{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:57:48Z","timestamp":1743026268194,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319221762"},{"type":"electronic","value":"9783319221779"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22177-9_12","type":"book-chapter","created":{"date-parts":[[2015,8,3]],"date-time":"2015-08-03T10:05:43Z","timestamp":1438596343000},"page":"146-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Complexity of Suffix-Free Regular Languages"],"prefix":"10.1007","author":[{"given":"Janusz","family":"Brzozowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"issue":"2","key":"12_CR1","first-page":"445","volume":"19","author":"T Ang","year":"2009","unstructured":"Ang, T., Brzozowski, J.: Languages convex with respect to binary relations, and their closure properties. Acta Cybernet. 19(2), 445\u2013464 (2009)","journal-title":"Acta Cybernet."},{"key":"12_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195768","volume-title":"Codes and Automata","author":"J Berstel","year":"2009","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press, Cambridge (2009)"},{"issue":"1\/2","key":"12_CR3","first-page":"71","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)","journal-title":"J. Autom. Lang. Comb."},{"issue":"6","key":"12_CR4","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1142\/S0129054113400133","volume":"24","author":"J Brzozowski","year":"2013","unstructured":"Brzozowski, J.: In search of the most complex regular languages. Int. J. Found. Comput. Sc. 24(6), 691\u2013708 (2013)","journal-title":"Int. J. Found. Comput. Sc."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-319-09704-6_9","volume-title":"Descriptional Complexity of Formal Systems","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Davies, G.: Most complex regular right-ideal languages. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 90\u2013101. Springer, Heidelberg (2014)"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Brzozowski, J., Davies, S.: Quotient complexities of atoms in regular ideal languages (2015). http:\/\/arxiv.org\/abs\/1503.02208","DOI":"10.14232\/actacyb.22.2.2015.4"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Brzozowski, J., Davies, S., Liu, B.Y.V.: Most complex regular ideals (2015). (in preparation)","DOI":"10.46298\/dmtcs.1343"},{"key":"12_CR8","doi-asserted-by":"crossref","first-page":"507","DOI":"10.14232\/actacyb.21.4.2014.1","volume":"21","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free regular languages. Acta Cybernet. 21, 507\u2013527 (2014)","journal-title":"Acta Cybernet."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2012.04.011","volume":"449","author":"J Brzozowski","year":"2012","unstructured":"Brzozowski, J., Li, B., Ye, Y.: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. Theoret. Comput. Sci. 449, 37\u201353 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Brzozowski, J., Szyku\u0142a, M.: Complexity of suffix-free regular languages (2015). http:\/\/arxiv.org\/abs\/1504.05159","DOI":"10.1007\/978-3-319-22177-9_12"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-319-19225-3_3","volume-title":"DCFS 2015","author":"J Brzozowski","year":"2015","unstructured":"Brzozowski, J., Szyku\u0142a, M.: Upper bound for syntactic complexity of suffix-free languages. In: Okhotin, A., Shallit, J. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 33\u201345. Springer, Heidelberg (2015). http:\/\/arxiv.org\/abs\/1412.2281"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.016","volume":"539","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Tamm, H.: Theory of \u00e1tomata. Theoret. Comput. Sci. 539, 13\u201327 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-22321-1_11","volume-title":"Developments in Language Theory","author":"J Brzozowski","year":"2011","unstructured":"Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 117\u2013128. Springer, Heidelberg (2011)"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-642-25929-6_9","volume-title":"Mathematical and Engineering Methods in Computer Science","author":"R Cmorik","year":"2012","unstructured":"Cmorik, R., Jir\u00e1skov\u00e1, G.: Basic operations on binary suffix-free languages. In: Kot\u00e1sek, Z., Bouda, J., \u010cern\u00e1, I., Sekanina, L., Vojnar, T., Anto\u0161, D. (eds.) MEMICS 2011. LNCS, vol. 7119, pp. 94\u2013102. Springer, Heidelberg (2012)"},{"issue":"27\u201329","key":"12_CR15","doi-asserted-by":"publisher","first-page":"2537","DOI":"10.1016\/j.tcs.2008.12.054","volume":"410","author":"YS Han","year":"2009","unstructured":"Han, Y.S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoret. Comput. Sci. 410(27\u201329), 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR16","unstructured":"Iv\u00e1n, S.: Complexity of atoms, combinatorially (2015). http:\/\/arxiv.org\/abs\/1404.6632"},{"key":"12_CR17","first-page":"151","volume-title":"NMCA","author":"G Jir\u00e1skov\u00e1","year":"2009","unstructured":"Jir\u00e1skov\u00e1, G., Olej\u00e1r, P.: State complexity of union and intersection of binary suffix-free languages. In: Bordihn, H., et al. (eds.) NMCA, pp. 151\u2013166. Austrian Computer Society, Wien (2009)"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"E Leiss","year":"2009","unstructured":"Leiss, E.: Succinct representation of regular languages by boolean automata. Theoret. Comput. Sci. 13, 323\u2013330 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR19","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). (Russian): English translation: Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"12_CR20","first-page":"7","volume":"2","author":"BG Mirkin","year":"1966","unstructured":"Mirkin, B.G.: On dual automata. Kibernetika (Kiev) 2, 7\u201310 (1966). (Russian): English translation: Cybernetics 2, 6\u20139 (1966)","journal-title":"Kibernetika (Kiev)"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-642-59136-5_10","volume-title":"Handbook of Formal Languages","author":"J-E Pin","year":"1997","unstructured":"Pin, J.-E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 679\u2013746. Springer, New York (1997)"},{"key":"12_CR22","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. Theoret. Comput. Sci. 125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR23","first-page":"221","volume":"6","author":"S Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb. 6, 221\u2013234 (2001)","journal-title":"J. Autom. Lang. Comb."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22177-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T20:23:06Z","timestamp":1674246186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22177-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319221762","9783319221779"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22177-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"4 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}