Geodesic
On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 59-64.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider complete $q$-ary trees of height $H$ with vertices marked by random independent marks taking values from some finite set. The number of pairs of paths having length $s$ and identical sequences of vertex marks is investigated. For the distribution of this number we propose sufficient conditions of asymptotic normality for the case when $H\to\infty$ and parameters $s$ and $q$ may vary. 
@article{MVK_2021_12_a3,
     author = {V. G. Mikhailov and V. I. Kruglov},
     title = {On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {59--64},
     publisher = {mathdoc},
     volume = {12},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_a3/}
}
TY  - JOUR
AU  - V. G. Mikhailov
AU  - V. I. Kruglov
TI  - On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 59
EP  - 64
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_a3/
LA  - ru
ID  - MVK_2021_12_a3
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%A V. I. Kruglov
%T On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
%J Matematičeskie voprosy kriptografii
%D 2021
%P 59-64
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_a3/
%G ru
%F MVK_2021_12_a3
V. G. Mikhailov; V. I. Kruglov. On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree. Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 59-64. http://geodesic.mathdoc.fr/item/MVK_2021_12_a3/

[1] Hoffmann C. M., O'Donnell M. J., “Pattern matching in trees”, J. ACM, 29:1 (1982), 68–95 | DOI | Zbl

[2] Zubkov A. M., Kruglov V. I., “Povtoreniya tsepochek na binarnom dereve so sluchainymi metkami vershin”, Diskretnaya matematika, 27:4 (2015), 38–48

[3] Kruglov V., Zubkov A., “Number of pairs of template matchings in $q$-ary tree with randomly marked vertices”, Analytical and Computational Methods in Probability Theory, Lect. Notes Comput. Sci., 10684, Springer, 2017, 336–346 | DOI | Zbl

[4] Kruglov V. I., “Povtoreniya tsepochek na $q$-ichnom dereve so sluchainymi metkami vershin”, Diskretnaya matematika, 30:3 (2018), 48–67 | DOI | MR | Zbl

[5] Guibas L. J., Odlyzko A. M., “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb., 53:1 (1980), 241–262 | DOI | Zbl

[6] Karlin S., Ost F., “Counts of long aligned word matches among random letter sequences”, Adv. Appl. Probab., 19:2 (1987), 293–351 | DOI | MR | Zbl

[7] Karnin E. D., “The first repetition of a pattern in a symmetric Bernoulli sequence”, J. Appl. Prob., 20:2 (1983), 413–418 | DOI | MR | Zbl

[8] Steyaert J.-M., Flajolet P., “Patterns and pattern-matching in trees: an analysis”, Inf. and Control, 58:1 (1983), 19–58 | DOI | Zbl

[9] Singh G., Smolka S.A., Ramakrishnan I.V., “Distributed algorithms for tree pattern matching”, Lect. Notes Comput. Sci., 312, 1988, 92–107 | DOI | Zbl

[10] Tahraoui M.A., Pinel-Sauvagnat K., Laitang C., Boughanem M., Kheddouci H., Ning L., “A survey on tree matching and XML retrieval”, Computer Science Review, 8 (2013), 1–23 | DOI | Zbl

[11] Zubkov A. M., Mikhailov V. G., “Predelnye raspredeleniya sluchainykh velichin, svyazannykh s dlinnymi povtoreniyami v posledovatelnosti nezavisimykh ispytanii”, Teoriya veroyatn. i ee primen., 19:1 (1974), 173–181 | Zbl

[12] Mikhailov V. G., “Otsenka tochnosti slozhnoi puassonovskoi approksimatsii dlya raspredeleniya chisla sovpadayuschikh tsepochek”, Teoriya veroyatn. i ee primen., 46:4 (2001), 713–723 | Zbl

[13] Janson S., “Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs”, Ann. Probab., 16:1 (1988), 306–312 | DOI

[14] Mikhailov V. G., “Ob odnoi teoreme Yansona”, Teoriya veroyatn. i ee primen., 36:1 (1991), 168–170 | MR