Asymptotics of relaxed $k$-ary trees

Abstract

A relaxed $k$-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree $k$. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed $k$-ary tree with $n$ nodes for $n\to \infty$. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term $e^{c{n}^{1/3}}$ appears in all these cases. We also derive the recurrences for compacted $k$-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.

12 pages, 3 figures, 3 tables