{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T23:42:01Z","timestamp":1775000521670,"version":"3.50.1"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p> In this paper we consider the state complexity of an operation on formal languages, root(L). This naturally entails the discussion of the monoid of transformations of a finite set. We obtain good upper and lower bounds on the state complexity of root(L) over alphabets of all sizes. As well, we present an application of these results to the problem of 2DFA-DFA conversion. <\/jats:p>","DOI":"10.1142\/s0129054105003157","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"547-563","source":"Crossref","is-referenced-by-count":13,"title":["STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET"],"prefix":"10.1142","volume":"16","author":[{"given":"BRYAN","family":"KRAWETZ","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada"}]},{"given":"JOHN","family":"LAWRENCE","sequence":"additional","affiliation":[{"name":"Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada"}]},{"given":"JEFFREY","family":"SHALLIT","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Algorithmic Number Theory, Volume 1: Efficient Algorithms","volume":"1","author":"Bach E.","year":"1996"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01371727"},{"key":"rf3","unstructured":"J.\u00a0D\u00e9nes, Theory of Graphs: Proc. Colloq. Graph Theory (1966) (Academic Press, 1968)\u00a0pp. 65\u201375."},{"key":"rf4","unstructured":"J.\u00a0D\u00e9nes, Permutations: Actes du Colloque sur Les Permutations, (1972) (Gauthier-Villars, 1972)\u00a0pp. 117\u2013120."},{"key":"rf5","doi-asserted-by":"crossref","unstructured":"M.\u00a0Holzer and B.\u00a0K\u00f6nig, Proc. DLT 2002, LNCS\u00a02450 (Springer-Verlag, 2003)\u00a0pp. 258\u2013269.","DOI":"10.1007\/3-540-45005-X_22"},{"key":"rf6","series-title":"LNCS","volume-title":"Proc. DLT 2003","volume":"2710","author":"Holzer M.","year":"2003"},{"key":"rf7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf10","unstructured":"B.\u00a0Krawetz, J.\u00a0Lawrence and J.\u00a0Shallit, CIAA 2004, LNCS\u00a03317 (Springer-Verlag, 2005)\u00a0pp. 215\u2013226."},{"key":"rf12","first-page":"1211","volume":"20","author":"Moore F. R.","journal-title":"IEEE Trans. Comput."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60408-9_18"},{"key":"rf15","author":"Salomaa A.","journal-title":"Ann. Acad. Scient. Fenn."},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00227-4"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0198"},{"key":"rf18","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4064\/aa-37-1-321-331","volume":"37","author":"Szalay M.","journal-title":"Acta Arith."},{"key":"rf19","first-page":"221","volume":"6","author":"Yu S.","journal-title":"J. Aut. Lang. and Comb."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2787"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:39:49Z","timestamp":1565138389000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":17,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0129054105003157"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003157","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}