{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T17:32:25Z","timestamp":1760981545363},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            For the register function for\n            <jats:italic>t<\/jats:italic>\n            -ary trees, recently introduced by Auber et al., we prove that the average is log\n            <jats:sub>4<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1), if all such trees with\n            <jats:italic>n<\/jats:italic>\n            internal nodes are considered to be equally likely.This result remains true for rooted trees where the set of possible out-degrees is finite. Furthermore we obtain exponential tail estimates for the distribution of the register function. Thus, the distribution is highly concentrated around the mean value.\n          <\/jats:p>","DOI":"10.1145\/1159892.1159894","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"318-334","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The register function for\n            <i>t<\/i>\n            -ary trees"],"prefix":"10.1145","volume":"2","author":[{"given":"Michael","family":"Drmota","sequence":"first","affiliation":[{"name":"Vienna University of Technology, Vienna, Austria"}]},{"given":"Helmut","family":"Prodinger","sequence":"additional","affiliation":[{"name":"University of Stellenbosch"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"-M","author":"Auber D.","year":"2004","unstructured":"Auber , D. , Domenger , J.-P. , Delest , M. , Duchon , P. , and F\u00e9dou , J . -M . 2004 . New Strahler numbers for rooted plane trees. In Mathematics and Computer Science III. Birk\u00e4user, Basel , 203-- 215. Auber, D., Domenger, J.-P., Delest, M., Duchon, P., and F\u00e9dou, J.-M. 2004. New Strahler numbers for rooted plane trees. In Mathematics and Computer Science III. Birk\u00e4user, Basel, 203-- 215."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1996300504431"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/368892.368907"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403019"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215046"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90009-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1130\/0016-7606(1945)56[275:EDOSAT]2.0.CO;2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289094"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90009-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00192-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0601005"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10052"},{"key":"e_1_2_1_13_1","first-page":"180","article-title":"Some analytic techniques for the investigation of the asymptotic behavior of tree parameters","volume":"47","author":"Prodinger H.","year":"1992","unstructured":"Prodinger , H. 1992 . Some analytic techniques for the investigation of the asymptotic behavior of tree parameters . EATCS Bull. 47 , 180 -- 199 . Prodinger, H. 1992. Some analytic techniques for the investigation of the asymptotic behavior of tree parameters. EATCS Bull. 47, 180--199.","journal-title":"EATCS Bull."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00269-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1130\/0016-7606(1952)63[1117:HAAOET]2.0.CO;2"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Comput. Science","volume-title":"Proceedings of the Colloquium on Trees in Algebra and Programming","author":"Viennot G. X.","unstructured":"Viennot , G. X. 1990. Trees everywhere . In Proceedings of the Colloquium on Trees in Algebra and Programming . Lecture Notes in Comput. Science , vol. 431 . Springer-Verlag , Berlin, Germany , 18-- 41. Viennot, G. X. 1990. Trees everywhere. In Proceedings of the Colloquium on Trees in Algebra and Programming. Lecture Notes in Comput. Science, vol. 431. Springer-Verlag, Berlin, Germany, 18-- 41."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/27\/2\/014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90047-L"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1159892.1159894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:42:25Z","timestamp":1672260145000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1159892.1159894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1159892.1159894"],"URL":"https:\/\/doi.org\/10.1145\/1159892.1159894","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}