{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:16Z","timestamp":1759637836644,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319601335"},{"type":"electronic","value":"9783319601342"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-60134-2_7","type":"book-chapter","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T12:53:09Z","timestamp":1495889589000},"page":"76-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Bifix-Free Regular Languages"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ferens","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":[[2017,5,28]]},"reference":[{"key":"7_CR1","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":"7_CR2","first-page":"71","volume":"15","author":"JA Brzozowski","year":"2010","unstructured":"Brzozowski, J.A.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1\/2), 71\u201389 (2010)","journal-title":"J. Autom. Lang. Comb."},{"issue":"6","key":"7_CR3","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. Sc. 24(6), 691\u2013708 (2013)","journal-title":"Int. J. Found. Comput. Sc."},{"key":"7_CR4","unstructured":"Brzozowski, J.A., Davies, S., Liu, B.Y.V.: Most complex regular ideals (2015). http:\/\/arxiv.org\/abs\/1511.00157"},{"issue":"4","key":"7_CR5","doi-asserted-by":"publisher","first-page":"507","DOI":"10.14232\/actacyb.21.4.2014.1","volume":"21","author":"JA Brzozowski","year":"2014","unstructured":"Brzozowski, J.A., Jir\u00e1skov\u00e1, G., Li, B., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free regular languages. Acta Cyber. 21(4), 507\u2013527 (2014)","journal-title":"Acta Cyber."},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2012.04.011","volume":"449","author":"JA Brzozowski","year":"2012","unstructured":"Brzozowski, J.A., 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":"7_CR7","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/j.ic.2010.11.009","volume":"209","author":"JA Brzozowski","year":"2011","unstructured":"Brzozowski, J.A., Shallit, J., Xu, Z.: Decision problems for convex languages. Inf. Comput. 209, 353\u2013367 (2011)","journal-title":"Inf. Comput."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Sinnamon, C.: Complexity of Prefix-Convex Regular Languages (2017, to appear). http:\/\/arxiv.org\/abs\/1605.06697","DOI":"10.1007\/978-3-319-60134-2_5"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Sinnamon, C.: Most Complex Non-Returning Regular Languages (2017). http:\/\/arxiv.org\/abs\/1701.03944","DOI":"10.1007\/978-3-319-60252-3_7"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-319-22177-9_12","volume-title":"Fundamentals of Computation Theory","author":"J Brzozowski","year":"2015","unstructured":"Brzozowski, J., Szyku\u0142a, M.: Complexity of suffix-free regular languages. In: Kosowski, A., Walukiewicz, I. (eds.) FCT 2015. LNCS, vol. 9210, pp. 146\u2013159. Springer, Cham (2015). doi:10.1007\/978-3-319-22177-9_12"},{"key":"7_CR11","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. Theoret. Comput. Sci. 539, 13\u201327 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR12","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). doi:10.1007\/978-3-642-25929-6_9"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.3233\/FI-2016-1326","volume":"144","author":"HS Eom","year":"2016","unstructured":"Eom, H.S., Han, Y.S., Jir\u00e1skov\u00e1, G.: State complexity of basic operations on non-returning regular languages. Fundam. Informaticae 144(2), 161\u2013182 (2016)","journal-title":"Fundam. Informaticae"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Ferens, R., Szyku\u0142a, M.: Complexity of bifix-free regular languages (2017). http:\/\/arxiv.org\/abs\/1701.03768","DOI":"10.1007\/978-3-319-60134-2_7"},{"key":"7_CR15","unstructured":"The GAP Group: GAP - Groups, Algorithms, and Programming (2016). http:\/\/www.gap-system.org"},{"issue":"5","key":"7_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."},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-85780-8_34","volume-title":"Developments in Language Theory","author":"G Jir\u00e1skov\u00e1","year":"2008","unstructured":"Jir\u00e1skov\u00e1, G.: On the state complexity of complements, stars, and reversals of regular languages. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 431\u2013442. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-85780-8_34"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-319-08846-4_17","volume-title":"Implementation and Application of Automata","author":"G Jir\u00e1skov\u00e1","year":"2014","unstructured":"Jir\u00e1skov\u00e1, G., Palmovsk\u00fd, M., \u0160ebej, J.: Kleene closure on regular and prefix-free languages. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 226\u2013237. Springer, Cham (2014). doi:10.1007\/978-3-319-08846-4_17"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"J\u00fcrgensen, H., Konstantinidis, S.: Codes. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Word, Language, Grammar, vol. 1, pp. 511\u2013607. Springer, Heidelberg (1997)","DOI":"10.1007\/978-3-642-59136-5_8"},{"key":"7_CR20","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.A.: Counter-Free Automata. The MIT Press, Cambridge (1971). (M.I.T. Research Monograph No. 65)"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Pin, J.E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Word, Language, Grammar, vol. 1, pp. 679\u2013746. Springer, New York, USA (1997)","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"7_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-642-39310-5_25","volume-title":"Descriptional Complexity of Formal Systems","author":"J \u0160ebej","year":"2013","unstructured":"\u0160ebej, J.: Reversal on regular languages and descriptional complexity. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 265\u2013276. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-39310-5_25"},{"key":"7_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/978-3-319-60134-2_17","volume-title":"CIAA 2017","author":"M Szyku\u0142a","year":"2017","unstructured":"Szyku\u0142a, M., Wittnebel, J.: Syntactic complexity of bifix-free languages. In: Carayol, A., Nicaud, C. (eds.) CIAA 2017. LNCS, vol. 10329, pp. 201\u2013212. Springer, Cham (2017)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60134-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:31:18Z","timestamp":1710343878000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-60134-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319601335","9783319601342"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60134-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"28 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marne-la-Vall\u00e9e","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ciaa17.univ-mlv.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}