# zbMATH — the first resource for mathematics

Some results on V-ary asymmetric tries. (English) Zbl 0637.68072
Tries (radix search tries) find many applications in computer science and telecommunications. It is assumed that a trie is built over an alphabet $$U=\{\sigma_ 1,...,\sigma_ V\}$$ (V-ary trie), and n (possible infinite) strings of elements from U (i.e., keys) are stored in external nodes of the trie. The occurrence of an element $$\sigma_ i$$ in a key is represented by a probability $$p_ i$$ (asymmetric trie). Our main interest is to compute all moments of the depth of a leaf (external node) in a random family of tries.
By solving a system of recurrences we find an exact formula for all factorial moments of the depth, and - using the Mellin transform technique - we derive asymptotic approximations for them. We prove that the mth factorial moment of the depth of a leaf in a trie with n keys is equal to $$\alpha$$ ln$${}^ m n+\beta \ln^{m-1} n+O(\ln^{m-2} n)$$, where the constants $$\alpha$$ and $$\beta$$ are functions of the probabilities, $$p_ i$$, $$i=1,...,V$$. In particular, we show that for symmetric tries the variance of the depth is O(1), while for asymmetric tries it is $$\alpha$$ ln n$$+O(1)$$, and we determine explicitly the constant O(1).
These results extend previous analyses by D. Knuth [The art of computer programming. Vol. 3: S25-29 (1986).
[For the entire collection see Zbl 0578.00003.]
Let’s start with the definitions of some notions considered in the paper. An infix code is a nonempty subset C of $$X^+$$ such that $$(xuy\in C \& u\in C \Rightarrow x=y=1).$$ If $$L\subset X^*$$, $$u\in X^*$$ let $$L..u=\{(x,y)|$$ $$x,y\in X^*$$, xuy$$\in L\}$$. The syntactic congruence $$P_ L$$ is defined by $$u\equiv v (P_ L)\Leftrightarrow$$ $$L..u=L..v$$. The syntactic monoid of L is $$syn(L)=X^*/P_ L.$$
The first part of the paper establishes the following results related to an infix code C: (1) syn(C) is subdirectly irreducible; (2) if C is finite, then syn(C) is a finite subdirectly irreducible nil monoid and $$| syn(C)| \geq 3$$; (3) conversely, every finite subdirectly irreducible nil monoid M with $$| M| \geq 3$$ is isomorphic with syn(C) where C is finite; (4) if C is infinite context-free then syn(C) is not a nil monoid; (5) if C is infinite (but not context-free) then syn(C) can still be a nil monoid - even an infinite one - as in the case of Thue code.
The second part is devoted to the study of the reflective infix codes in relations with star reflective codes.
Reviewer: V.Coardoş

##### MSC:
 68P10 Searching and sorting 68Q25 Analysis of algorithms and problem complexity 60D05 Geometric probability and stochastic geometry 68Q45 Formal languages and automata
Full Text: