完整後設資料紀錄
DC 欄位語言
dc.contributor.authorFuchs, M.en_US
dc.contributor.authorLee, C. -K.en_US
dc.contributor.authorYu, G. -R.en_US
dc.date.accessioned2017-04-21T06:56:30Z-
dc.date.available2017-04-21T06:56:30Z-
dc.date.issued2016-04-04en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2016.02.007en_US
dc.identifier.urihttp://hdl.handle.net/11536/133423-
dc.description.abstractIn this paper, we consider the number of 2-protected nodes in random digital trees. Results for the mean and variance of this number for tries have been obtained by Gaither et al. (2012) [11] and Gaither and Ward (2013) [10] and for the mean in digital search trees by Du and Prodinger (2012) [5]. In this short note, we show that these previous results and extensions such as the variance in digital search trees and limit laws in both cases can be derived in a systematic way by recent approaches of Fuchs et al. (2012; 2014) [8, 15] and Fuchs and Lee (2014) [9]. Interestingly, the results for the moments we obtain by our approach are quite different from the previous ones and contain divergent series which have values by appealing to the theory of Abel summability. We also show that our tools apply to PATRICIA tries, for which the number of 2-protected nodes has not been investigated so far. (C) 2016 Elsevier B.V. All rights reserved.en_US
dc.language.isoen_USen_US
dc.subjectData structuresen_US
dc.subjectDigital treesen_US
dc.subjectAnalytic combinatoricsen_US
dc.subjectMomentsen_US
dc.subjectLimit theoremsen_US
dc.subjectAbel summabilityen_US
dc.titleOn 2-protected nodes in random digital treesen_US
dc.identifier.doi10.1016/j.tcs.2016.02.007en_US
dc.identifier.journalTHEORETICAL COMPUTER SCIENCEen_US
dc.citation.volume622en_US
dc.citation.spage111en_US
dc.citation.epage122en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000371939200008en_US
顯示於類別:期刊論文