Asymptotics of relaxed \(k\)-ary trees

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-04
Main Authors: Manosij Ghosh Dastidar, Wallner, Michael
Format: Article
Language:English
Subjects:
Asymptotic properties
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422