{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T18:07:24Z","timestamp":1769969244677,"version":"3.49.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319946306","type":"print"},{"value":"9783319946313","type":"electronic"}],"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_16","type":"book-chapter","created":{"date-parts":[[2018,7,10]],"date-time":"2018-07-10T06:09:52Z","timestamp":1531202992000},"page":"188-199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Unambiguous Operations on Deterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-77313-1_5","volume-title":"Language and Automata Theory and Applications","author":"E Bakinova","year":"2018","unstructured":"Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A., Sazhneva, E.: Formal languages over GF(2). In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 68\u201379. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77313-1_5"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.jcss.2017.05.011","volume":"89","author":"JA Brzozowski","year":"2017","unstructured":"Brzozowski, J.A., Szyku\u0142a, M.: Complexity of suffix-free regular languages. J. Comput. Syst. Sci. 89, 270\u2013287 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2017.05.011","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR3","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). https:\/\/doi.org\/10.1007\/978-3-642-25929-6_9"},{"issue":"5","key":"16_CR4","doi-asserted-by":"publisher","first-page":"653","DOI":"10.3217\/jucs-016-05-0653","volume":"16","author":"M Daley","year":"2010","unstructured":"Daley, M., Domaratzki, M., Salomaa, K.: Orthogonal concatenation: language equations and state complexity. J. Univers. Comput. Sci. 16(5), 653\u2013675 (2010). https:\/\/doi.org\/10.3217\/jucs-016-05-0653","journal-title":"J. Univers. Comput. Sci."},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"2537","DOI":"10.1016\/j.tcs.2008.12.054","volume":"410","author":"Y-S Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoret. Comput. Sci. 410, 2537\u20132548 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.12.054","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.4204\/EPTCS.31.21","volume":"31","author":"Yo-Sub Han","year":"2010","unstructured":"Han, Y.-S., Salomaa, K.: Nondeterministic state complexity for suffix-free regular languages. In: DCFS 2010, EPTCS, vol. 31, pp. 189\u2013196 (2010). https:\/\/doi.org\/10.4204\/EPTCS.31.21","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"16_CR7","unstructured":"Han, Y.-S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: Automata, Formal Languages, and Related Topics, pp. 99\u2013115 (2009)"},{"issue":"1\u20132","key":"16_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.3233\/FI-2009-0008","volume":"90","author":"Y-S Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K., Wood, D.: Nondeterministic state complexity of basic operations for prefix-free regular languages. Fundamenta Informaticae 90(1\u20132), 93\u2013106 (2009). https:\/\/doi.org\/10.3233\/FI-2009-0008","journal-title":"Fundamenta Informaticae"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1142\/S0129054103002199","volume":"14","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14, 1087\u20131102 (2003). https:\/\/doi.org\/10.1142\/S0129054103002199","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1142\/S0129054105003133","volume":"16","author":"J Jir\u00e1sek","year":"2005","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., Szabari, A.: State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. 16(3), 511\u2013529 (2005). https:\/\/doi.org\/10.1142\/S0129054105003133","journal-title":"Int. J. Found. Comput. Sci."},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-662-53132-7_20","volume-title":"Developments in Language Theory","author":"J Jir\u00e1sek","year":"2016","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., \u0160ebej, J.: Operations on unambiguous finite automata. In: Brlek, S., Reutenauer, C. (eds.) DLT 2016. LNCS, vol. 9840, pp. 243\u2013255. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53132-7_20"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.4204\/EPTCS.31.22","volume":"31","author":"Galina Jir\u00e1skov\u00e1","year":"2010","unstructured":"Jir\u00e1skov\u00e1, G., Krausov\u00e1, M.: Complexity in prefix-free regular languages. In: DCFS 2010, EPTCS, vol. 31, pp. 197\u2013204. https:\/\/doi.org\/10.4204\/EPTCS.31.22","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"16_CR13","unstructured":"Jir\u00e1skov\u00e1, G., Olej\u00e1r, P.: State complexity of intersection and union of suffix-free languages and descriptional complexity. In: NCMA 2009, books@ocg.at, vol. 256, 151\u2013166 (2009)"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ic.2016.12.007","volume":"253","author":"G Jir\u00e1skov\u00e1","year":"2017","unstructured":"Jir\u00e1skov\u00e1, G., Okhotin, A.: On the state complexity of operations on two-way finite automata. Inf. Comput. 253(1), 36\u201363 (2017). https:\/\/doi.org\/10.1016\/j.ic.2016.12.007","journal-title":"Inf. Comput."},{"issue":"1\u20134","key":"16_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.3233\/FI-2011-540","volume":"110","author":"M Kunc","year":"2011","unstructured":"Kunc, M., Okhotin, A.: State complexity of union and intersection for two-way nondeterministic finite automata. Fundamenta Informaticae 110(1\u20134), 231\u2013239 (2011). https:\/\/doi.org\/10.3233\/FI-2011-540","journal-title":"Fundamenta Informaticae"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.tcs.2012.04.010","volume":"449","author":"M Kunc","year":"2012","unstructured":"Kunc, M., Okhotin, A.: State complexity of operations on two-way deterministic finite automata over a unary alphabet. Theoret. Comput. Sci. 449, 106\u2013118 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.04.010","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR17","first-page":"1373","volume":"11","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ic.2012.01.003","volume":"212","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A.: Unambiguous finite automata over a unary alphabet. Inf. Comput. 212, 15\u201336 (2012). https:\/\/doi.org\/10.1016\/j.ic.2012.01.003","journal-title":"Inf. Comput."},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S012905410200100X","volume":"13","author":"G Pighizzini","year":"2002","unstructured":"Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal\u2019s function. Int. J. Found. Comput. Sci. 13(1), 145\u2013159 (2002). https:\/\/doi.org\/10.1142\/S012905410200100X","journal-title":"Int. J. Found. Comput. Sci."},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.1016\/j.tcs.2009.02.035","volume":"410","author":"N Rampersad","year":"2009","unstructured":"Rampersad, N., Ravikumar, B., Santean, N., Shallit, J.: State complexity of unique rational operations. Theoret. Comput. Sci. 410, 2431\u20132441 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.02.035","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR21","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 complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315\u2013328 (1994). https:\/\/doi.org\/10.1016\/0304-3975(92)00011-F","journal-title":"Theoret. 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_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:16:39Z","timestamp":1710324999000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94631-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319946306","9783319946313"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94631-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"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"}}]}}