{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:47Z","timestamp":1759638347737},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642223204"},{"type":"electronic","value":"9783642223211"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22321-1_11","type":"book-chapter","created":{"date-parts":[[2011,7,15]],"date-time":"2011-07-15T03:58:48Z","timestamp":1310702328000},"page":"117-128","source":"Crossref","is-referenced-by-count":21,"title":["Syntactic Complexity of Ideal and Closed Languages"],"prefix":"10.1007","author":[{"given":"Janusz","family":"Brzozowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuli","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"8\/9","key":"11_CR1","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00236-006-0006-z","volume":"42","author":"S. Bozapalidis","year":"2006","unstructured":"Bozapalidis, S., Kalampakas, A.: Recognizability of graph and pattern languages. Acta Inform.\u00a042(8\/9), 553\u2013581 (2006)","journal-title":"Acta Inform."},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-03564-7_12","volume-title":"Algebraic Informatics","author":"S. Bozapalidis","year":"2009","unstructured":"Bozapalidis, S., Kalampakas, A.: On the complexity of the syntax of tree languages. In: Bozapalidis, S., Rahonis, G. (eds.) CAI 2009. LNCS, vol.\u00a05725, pp. 189\u2013203. Springer, Heidelberg (2009)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita\/2010014","volume":"44","author":"S. Bozapalidis","year":"2010","unstructured":"Bozapalidis, S., Kalampakas, A.: On the syntactic complexity of tree series. RAIRO-Theor. Inf. Appl.\u00a044, 257\u2013279 (2010)","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"11_CR4","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, DCFS, pp. 25\u201342 (2009), Extended abstract at http:\/\/arxiv.org\/abs\/0907.4547"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-12200-2_20","volume-title":"LATIN 2010: Theoretical Informatics","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), Full paper at http:\/\/arxiv.org\/abs\/0908.2083"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-13182-0_8","volume-title":"Computer Science \u2013 Theory and Applications","author":"J. Brzozowski","year":"2010","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Zou, C.: Quotient complexity of closed languages. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol.\u00a06072, pp. 84\u201395. Springer, Heidelberg (2010)"},{"key":"11_CR7","unstructured":"Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages (October 2010), http:\/\/arxiv.org\/abs\/1010.3263"},{"key":"11_CR8","unstructured":"D\u00e9nes, J.: On transformations, transformation semigroups and graphs. In: Erd\u00f6s, P., Katona, G. (eds.) Theory of Graphs. Proceedings of the Colloquium on Graph Theory held at Tihany, 1966, pp. 65\u201375. Akad\u00e9miai Kiado (1968)"},{"key":"11_CR9","doi-asserted-by":"publisher","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.\u00a0327, 319\u2013347 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"11_CR10","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BF02124933","volume":"46","author":"M. Hoyer","year":"1895","unstructured":"Hoyer, M.: Verallgemeinerung zweier s\u00e4tze aus der theorie der substitutionengruppen. Math. Ann.\u00a046(4), 539\u2013544 (1895)","journal-title":"Math. Ann."},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-75414-5_13","volume-title":"Algebraic Informatics","author":"A. Kalampakas","year":"2007","unstructured":"Kalampakas, A.: The syntactic complexity of eulerian graphs. In: Bozapalidis, S., Rahonis, G. (eds.) CAI 2007. LNCS, vol.\u00a04728, pp. 208\u2013217. Springer, Heidelberg (2007)"},{"key":"11_CR12","unstructured":"Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set (2003), http:\/\/arxiv.org\/abs\/math\/0306416"},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","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.\u00a016(3), 547\u2013563 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"issue":"1970","key":"11_CR14","first-page":"1373","volume":"11","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. 11 , 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"11_CR15","unstructured":"Myhill, J.: Finite automata and representation of events. Wright Air Development Center Technical Report 57\u2013624 (1957)"},{"key":"11_CR16","doi-asserted-by":"publisher","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.\u00a09, 541\u2013544 (1958)","journal-title":"Proc. Amer. Math. Soc."},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"298","DOI":"10.4064\/fm-24-1-298-301","volume":"24","author":"S. Piccard","year":"1935","unstructured":"Piccard, S.: Sur les fonctions d\u00e9finies dans les ensembles finis quelconques. Fund. Math.\u00a024, 298\u2013301 (1935)","journal-title":"Fund. Math."},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01199686","volume":"11","author":"S. Piccard","year":"1938","unstructured":"Piccard, S.: Sur les bases du groupe sym\u00e9trique et du groupe alternant. Commentarii Mathematici Helvetici\u00a011(1), 1\u20138 (1938)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Restivo, A., Vaglica, R.: Automata with extremal minimality conditions. In: Gao, Y., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 399\u2013410. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14455-4_36"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"203","DOI":"10.2307\/2964675","volume":"25","author":"A. Salomaa","year":"1960","unstructured":"Salomaa, A.: A theorem concerning the composition of functions of several variables ranging over a finite set. J. Symbolic Logic\u00a025, 203\u2013208 (1960)","journal-title":"J. Symbolic Logic"},{"key":"11_CR21","unstructured":"Salomaa, A.: Some completeness criteria for sets of functions over a finite domain. Ann. Univ. Turkuensis, Ser. AI\u00a053 (1962)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Salomaa, A.: On basic groups for the set of functions over a finite domain. Ann. Acad. Scient. Fenn., Ser. A\u00a0338 (1963)","DOI":"10.5186\/aasfm.1964.338"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0304-3975(01)00227-4","volume":"292","author":"A. Salomaa","year":"2003","unstructured":"Salomaa, A.: Composition sequences for functions over a finite domain. Theoret. Comput. Sci.\u00a0292, 263\u2013281 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR24","doi-asserted-by":"crossref","first-page":"209","DOI":"10.4064\/fm-24-1-209-212","volume":"24","author":"X. Sierpi\u0144ski","year":"1935","unstructured":"Sierpi\u0144ski, X.: Sur les suites infinies de fonctions d\u00e9finies dans les ensembles quelconques. Fund. Math.\u00a024, 209\u2013212 (1935)","journal-title":"Fund. Math."},{"key":"11_CR25","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."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22321-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:27:37Z","timestamp":1560385657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22321-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642223204","9783642223211"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22321-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}