{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:26Z","timestamp":1759639046533},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540243182"},{"type":"electronic","value":"9783540305002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-30500-2_20","type":"book-chapter","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T16:39:36Z","timestamp":1267461576000},"page":"213-224","source":"Crossref","is-referenced-by-count":4,"title":["State Complexity and the Monoid of Transformations of a Finite Set"],"prefix":"10.1007","author":[{"given":"Bryan","family":"Krawetz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Lawrence","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","series-title":"Efficient Algorithms","volume-title":"Algorithmic Number Theory","author":"E. Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory. Efficient Algorithms, vol.\u00a01. The MIT Press, Cambridge (1996)"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01371727","volume":"26","author":"J.-C. Birget","year":"1993","unstructured":"Birget, J.-C.: State-complexity of finite-state devices, state compressibility and incompressibility. Math. Systems Theory\u00a026, 237\u2013269 (1993)","journal-title":"Math. Systems Theory"},{"key":"20_CR3","first-page":"65","volume-title":"Theory of Graphs: Proc. Colloq. Graph Theory (1966)","author":"J. D\u00e9nes","year":"1968","unstructured":"D\u00e9nes, J.: On transformations, transformation-semigroups and graphs. In: Theory of Graphs: Proc. Colloq. Graph Theory (1966), pp. 65\u201375. Academic Press, London (1968)"},{"key":"20_CR4","unstructured":"D\u00e9nes, J.: On a generalization of permutations: some properties of transformations. In: Permutations: Actes du Colloque sur Les Permutations, pp. 117\u2013120. Gauthier-Villars (1972)"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/3-540-45005-X_22","volume-title":"Developments in Language Theory","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., K\u00f6nig, B.: On deterministic finite automata and syntactic monoid size. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol.\u00a02450, pp. 258\u2013269. Springer, Heidelberg (2003)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/3-540-45007-6_28","volume-title":"Developments in Language Theory","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., K\u00f6nig, B.: On deterministic finite automata and syntactic monoid size, continued. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol.\u00a02710, pp. 349\u2013360. Springer, Heidelberg (2003)"},{"key":"20_CR7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"20_CR8","unstructured":"Krawetz, B.: Monoids and the state complexity of the operation root (L). Master\u2019s thesis, University of Waterloo (2003), Available at: http:\/\/www.math.uwaterloo.ca\/~shallit\/krawetz.ps"},{"key":"20_CR9","unstructured":"Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set (preprint) Available at: http:\/\/arxiv.org\/math\/0306416v1"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proc. 12th IEEE Symp. Switching and Automata Theory, pp. 188\u2013190 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata. IEEE Trans. Comput.\u00a020, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/978-3-642-60408-9_18","volume-title":"The Mathematics of Paul Erd\u00f6s","author":"J.-L. Nicolas","year":"1997","unstructured":"Nicolas, J.-L.: On Landau\u2019s function g(n). In: Graham, R.L., Nesetril, J. (eds.) The Mathematics of Paul Erd\u00f6s, pp. 228\u2013240. Springer, Heidelberg (1997)"},{"key":"20_CR13","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. I.\u00a0338 (1963)","DOI":"10.5186\/aasfm.1964.338"},{"key":"20_CR14","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. Comp. Sci.\u00a0292, 263\u2013281 (2003)","journal-title":"Theoret. Comp. Sci."},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4064\/aa-37-1-321-331","volume":"37","author":"M. Szalay","year":"1980","unstructured":"Szalay, M.: On the maximal order in Sn and S\u2217n. Acta Arith.\u00a037, 321\u2013331 (1980)","journal-title":"Acta Arith."},{"key":"20_CR16","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Aut. Lang. and Comb.\u00a06, 221\u2013234 (2001)","journal-title":"J. Aut. Lang. and Comb."},{"key":"20_CR17","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. Comp. Sci.\u00a0125, 315\u2013328 (1994)","journal-title":"Theoret. Comp. Sci."},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/inco.1998.2787","volume":"152","author":"G.-Q. Zhang","year":"1999","unstructured":"Zhang, G.-Q.: Automata, boolean matrices, and ultimate periodicity. Inform. Comput.\u00a0152, 138\u2013154 (1999)","journal-title":"Inform. Comput."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30500-2_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:57:11Z","timestamp":1605761831000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30500-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540243182","9783540305002"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30500-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}