{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:55:45Z","timestamp":1757454945103,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T00:00:00Z","timestamp":1501804800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/09\/N\/ST6\/01194"],"award-info":[{"award-number":["2013\/09\/N\/ST6\/01194"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["OGP000087"],"award-info":[{"award-number":["OGP000087"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9803-8","type":"journal-article","created":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T02:23:38Z","timestamp":1501813418000},"page":"1175-1202","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Syntactic Complexity of Regular Ideals"],"prefix":"10.1007","volume":"62","author":[{"given":"Janusz A.","family":"Brzozowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5349-468X","authenticated-orcid":false,"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[]},{"given":"Yuli","family":"Ye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,4]]},"reference":[{"issue":"2","key":"9803_CR1","first-page":"445","volume":"19","author":"T Ang","year":"2009","unstructured":"Ang, T., Brzozowski, J.A.: Languages convex with respect to binary relations, and their closure properties. Acta Cybernet. 19(2), 445\u2013464 (2009)","journal-title":"Acta Cybernet."},{"issue":"1\/2","key":"9803_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":"9803_CR3","doi-asserted-by":"crossref","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":"9803_CR4","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2012.10.055","volume":"470","author":"JA Brzozowski","year":"2013","unstructured":"Brzozowski, J.A., Jir\u00e1skov\u00e1, G., Li, B.: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 36\u201352 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"9803_CR5","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s00224-013-9515-7","volume":"54","author":"JA Brzozowski","year":"2014","unstructured":"Brzozowski, J.A., Jir\u00e1skov\u00e1, G., Zou, C.: Quotient complexity of closed languages. Theory Comput. Syst. 54, 277\u2013292 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"9803_CR6","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1142\/S0129054105003157","volume":"16","author":"JA Brzozowski","year":"2005","unstructured":"Brzozowski, J.A., Li, B.: Syntactic complexity of R- and J-trivial languages. Internat. J. Found. Comput. Sci. 16(3), 547\u2013563 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"9803_CR7","first-page":"83","volume":"17","author":"JA Brzozowski","year":"2012","unstructured":"Brzozowski, J.A., Li, B., Liu, D.: Syntactic complexities of six classes of star-free languages. J. Autom. Lang. Comb. 17, 83\u2013105 (2012)","journal-title":"J. Autom. Lang. Comb."},{"key":"9803_CR8","doi-asserted-by":"crossref","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":"9803_CR9","doi-asserted-by":"crossref","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":"9803_CR10","unstructured":"Brzozowski, J.A., Szyku\u0142a, M.: Large aperiodic semigroups. Int. J. Found. Comput. Sc. 26(7), 913\u2013931 (2015)"},{"key":"9803_CR11","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Szyku\u0142a, M: Upper bounds on syntactic complexity of left and two-sided ideals. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014, LNCS, vol. 8633, pp. 13\u201324. Springer (2014)","DOI":"10.1007\/978-3-319-09698-8_2"},{"key":"9803_CR12","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., 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 (2015). Full paper to appear in Information and Computation","DOI":"10.1007\/978-3-319-19225-3_3"},{"key":"9803_CR13","doi-asserted-by":"crossref","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":"9803_CR14","doi-asserted-by":"crossref","unstructured":"Brzozowski, J.A., Ye, Y.: Syntactic complexity of ideal and closed languages. In: Mauri, G., Leporati, A. (eds.) DLT 2011, LNCS, vol. 6795, pp. 117\u2013128. Springer (2011)","DOI":"10.1007\/978-3-642-22321-1_11"},{"key":"9803_CR15","doi-asserted-by":"crossref","unstructured":"C\u00e2mpeanu, C., Culik, K. II, Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) Automata implementation, LNCS, vol. 2214, pp. 60\u201370. Springer (2001)","DOI":"10.1007\/3-540-45526-4_6"},{"key":"9803_CR16","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C.: Automata for pattern matching. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 399\u2013462. Springer (1997)","DOI":"10.1007\/978-3-662-07675-0_9"},{"issue":"27\u201329","key":"9803_CR17","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). doi: 10.1016\/j.tcs.2008.12.054","journal-title":"Theoret. Comput. Sci."},{"key":"9803_CR18","unstructured":"Han, Y.S., Salomaa, K., Wood, D., \u00c9sik, Z., F\u00fcl\u00f6p, Z.: Operational state complexity of prefix-free regular languages. In: Automata, Formal Languages, and Related Topics, pp. 99\u2013115. University of Szeged, Hungary (2009)"},{"key":"9803_CR19","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.tcs.2004.04.010","volume":"327","author":"M Holzer","year":"2004","unstructured":"Holzer, M., K\u00f6nig, B.: On deterministic finite automata and syntactic monoid size. Theoret. Comput. Sci. 327, 319\u2013347 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9803_CR20","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1142\/S0129054105003157","volume":"16","author":"B Krawetz","year":"2005","unstructured":"Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set. Internat. J. Found. Comput. Sci. 16(3), 547\u2013563 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"9803_CR21","doi-asserted-by":"crossref","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 (1990)","DOI":"10.1007\/978-1-4612-3352-7_20"},{"key":"9803_CR22","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, (Russian) (1970). English translation: Soviet Math. Dokl. 11 (1970), 1373\u20131375","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9803_CR23","unstructured":"McNaughton, R., Papert, S.A.: Counter-free Automata (M.I.T. Research Monograph No. 65). The MIT Press (1971)"},{"key":"9803_CR24","unstructured":"Myhill, J.: Finite automata and representation of events. Wright Air Development Center Technical Report. 57\u2013624 (1957)"},{"key":"9803_CR25","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Amer. Math. Soc. 9, 541\u2013544 (1958)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"9803_CR26","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 12(3), 399\u2013410 (1965). doi: 10.1145\/321281.321292","journal-title":"J. ACM"},{"key":"9803_CR27","doi-asserted-by":"crossref","unstructured":"Perrin, D.: Finite automata. In: Van Leewen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 1\u201357. Elsevier (1990)","DOI":"10.1016\/B978-0-444-88074-1.50006-8"},{"issue":"1","key":"9803_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01199686","volume":"11","author":"S Piccard","year":"1938","unstructured":"Piccard, S.: Sur les bases du group sym\u00e9trique et du groupe alternant. Commentarii Mathematici Helvetici 11(1), 1\u20138 (1938)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"9803_CR29","doi-asserted-by":"crossref","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 (1997)","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"9803_CR30","doi-asserted-by":"crossref","first-page":"209","DOI":"10.4064\/fm-24-1-209-212","volume":"24","author":"W Sierpi\u0144ski","year":"1935","unstructured":"Sierpi\u0144ski, W.: Sur les suites infinies de fonctions d\u00e9finies dans les ensembles quelconques. Fund. Math. 24, 209\u2013212 (1935)","journal-title":"Fund. Math."},{"key":"9803_CR31","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 (2017). Full paper at arXiv: 1604.06936"},{"key":"9803_CR32","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41\u2013110. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"9803_CR33","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":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9803-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9803-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9803-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T21:02:25Z","timestamp":1569963745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9803-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,4]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9803"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9803-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,8,4]]}}}