{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:47:16Z","timestamp":1764841636324},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130885"},{"type":"electronic","value":"9783642130892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13089-2_1","type":"book-chapter","created":{"date-parts":[[2010,5,7]],"date-time":"2010-05-07T12:05:27Z","timestamp":1273233927000},"page":"1-15","source":"Crossref","is-referenced-by-count":4,"title":["Complexity in Convex Languages"],"prefix":"10.1007","author":[{"given":"Janusz","family":"Brzozowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"1_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.\u00a019(2), 445\u2013464 (2009)","journal-title":"Acta Cybernet."},{"key":"1_CR2","volume-title":"Theory of Codes","author":"J. Berstel","year":"1985","unstructured":"Berstel, J., Perrin, D.: Theory of Codes. Academic Press, London (1985)"},{"key":"1_CR3","series-title":"Encyclopedia of Mathematics and its Applications","volume-title":"Codes and Automata","author":"J. Berstel","year":"2010","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2010)"},{"issue":"4","key":"1_CR4","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J. Brzozowski","year":"1964","unstructured":"Brzozowski, J.: Derivatives of regular expressions. J. ACM\u00a011(4), 481\u2013494 (1964)","journal-title":"J. ACM"},{"key":"1_CR5","unstructured":"Brzozowski, J.: Quotient complexity of regular languages. In: Dassow, J., Pighizzini, G., Truthe, B. (eds.) Proceedings of the 11th International Workshop on Descriptional Complexity of Formal Systems, Magdeburg, Germany, Otto-von-Guericke-Universit\u00e4t, pp. 25\u201342 (2009), Extended abstract at \n                    \n                      http:\/\/arxiv.org\/abs\/0907.4547"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-642-12200-2_20","volume-title":"Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN)","author":"J. Brzozowski","year":"2010","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B.: Quotient complexity of ideal languages. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 208\u2013221. Springer, Heidelberg (2010)"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 5th International Computer Science Symposium in Russia, CSR","author":"J. Brzozowski","year":"2010","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Zou, C.: Quotient complexity of closed languages. In: Proceedings of the 5th International Computer Science Symposium in Russia, CSR. LNCS, Springer, Heidelberg (to appear, 2010), \n                    \n                      http:\/\/arxiv.org\/abs\/0912.1034"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-00982-2_21","volume-title":"Language and Automata Theory and Applications","author":"J. Brzozowski","year":"2009","unstructured":"Brzozowski, J., Shallit, J., Xu, Z.: Decision problems for convex languages. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 247\u2013258. Springer, Heidelberg (2009)"},{"key":"1_CR9","unstructured":"Brzozowski, J., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free languages (In preparation)"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"Automata Implementation","author":"C. C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Culik II, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol.\u00a02214, pp. 60\u201370. Springer, Heidelberg (2001)"},{"issue":"1","key":"1_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-0000(74)80034-6","volume":"9","author":"A. Gill","year":"1974","unstructured":"Gill, A., Kou, L.T.: Multiple-entry finite automata. J. Comput. Syst. Sci.\u00a09(1), 1\u201319 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/S0021-9800(69)80111-0","volume":"6","author":"L. Haines","year":"1969","unstructured":"Haines, L.: On free monoids partially ordered by embedding. J. Combin. Theory\u00a06(1), 94\u201398 (1969)","journal-title":"J. Combin. Theory"},{"issue":"27-29","key":"1_CR13","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.\u00a0410(27-29), 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR14","first-page":"99","volume-title":"Automata, Formal Languages, and Related Topics","author":"Y.S. Han","year":"2009","unstructured":"Han, Y.S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) Automata, Formal Languages, and Related Topics, pp. 99\u2013115. University of Szeged, Hungary (2009)"},{"issue":"2","key":"1_CR15","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"3","author":"G. Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc.\u00a03(2), 326\u2013336 (1952)","journal-title":"Proc. London Math. Soc."},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/978-3-642-59136-5_8","volume-title":"Handbook of Formal Languages, Word, Language, Grammar","author":"H. J\u00fcrgensen","year":"1997","unstructured":"J\u00fcrgensen, H., Konstantinidis, S.: Codes. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Word, Language, Grammar, vol.\u00a01, pp. 511\u2013607. Springer, Heidelberg (1997)"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1080\/00207169108803999","volume":"40","author":"H. J\u00fcrgensen","year":"1991","unstructured":"J\u00fcrgensen, H., Yu, S.S.: Relations on free monoids, their independent sets, and codes. Internat. J. Comput. Math.\u00a040, 17\u201346 (1991)","journal-title":"Internat. J. Comput. Math."},{"issue":"47-49","key":"1_CR18","doi-asserted-by":"publisher","first-page":"5010","DOI":"10.1016\/j.tcs.2009.07.049","volume":"410","author":"J.Y. Kao","year":"2009","unstructured":"Kao, J.Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both. Theoret. Comput. Sci.\u00a0410(47-49), 5010\u20135021 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0097-3165(72)90063-5","volume":"13","author":"J.B. Kruskal","year":"1972","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Combin. Theory A\u00a013(3), 297\u2013305 (1972)","journal-title":"J. Combin. Theory A"},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-1-4612-3352-7_20","volume-title":"Sequences: Combinatorics, Compression, Security, and Transmission","author":"A. Luca de","year":"1990","unstructured":"de Luca, A., Varricchio, S.: Some combinatorial properties of factorial languages. In: Capocelli, R. (ed.) Sequences: Combinatorics, Compression, Security, and Transmission, pp. 258\u2013266. Springer, Heidelberg (1990)"},{"key":"1_CR21","first-page":"1266","volume":"194","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR\u00a0194, 1266\u20131268 (1970) (Russian); English translation: Soviet Math. Dokl.\u00a011, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"3","key":"1_CR22","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1145\/321281.321292","volume":"12","author":"A. Paz","year":"1965","unstructured":"Paz, A., Peleg, B.: Ultimate-definite and symmetric-definite events and automata. J. ACM\u00a012(3), 399\u2013410 (1965)","journal-title":"J. ACM"},{"key":"1_CR23","series-title":"Oxford Lectures Series in Mathematics and its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198568209.001.0001","volume-title":"The Diophantine Frobenius Problem","author":"J.L. Ram\u00edrez Alfons\u00edn","year":"2005","unstructured":"Ram\u00edrez Alfons\u00edn, J.L.: The Diophantine Frobenius Problem. Oxford Lectures Series in Mathematics and its Applications, vol.\u00a030. Oxford University Press, Oxford (2005)"},{"key":"1_CR24","volume-title":"Free Monoids and Languages","author":"H.J. Shyr","year":"2001","unstructured":"Shyr, H.J.: Free Monoids and Languages. Hon Min Book Co., Taiwan (2001)"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0019-9958(74)80022-7","volume":"24","author":"H.J. Shyr","year":"1974","unstructured":"Shyr, H.J., Thierrin, G.: Hypercodes. Information and Control\u00a024, 45\u201354 (1974)","journal-title":"Information and Control"},{"key":"1_CR26","first-page":"481","volume-title":"Automata, Languages and Programming","author":"G. Thierrin","year":"1973","unstructured":"Thierrin, G.: Convex languages. In: Nivat, M. (ed.) Automata, Languages and Programming, pp. 481\u2013492. North-Holland, Amsterdam (1973)"},{"key":"1_CR27","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb.\u00a06, 221\u2013234 (2001)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2","key":"1_CR28","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.\u00a0125(2), 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13089-2_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:54:30Z","timestamp":1619783670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13089-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130885","9783642130892"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13089-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}