DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.15

Asymptotics of Relaxed k-Ary Trees

Authors: Manosij Ghosh Dastidar and Michael Wallner

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

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

Cite as

Manosij Ghosh Dastidar and Michael Wallner. Asymptotics of Relaxed k-Ary Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghoshdastidar_et_al:LIPIcs.AofA.2024.15,
  author =	{Ghosh Dastidar, Manosij and Wallner, Michael},
  title =	{{Asymptotics of Relaxed k-Ary Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.15},
  URN =		{urn:nbn:de:0030-drops-204506},
  doi =		{10.4230/LIPIcs.AofA.2024.15},
  annote =	{Keywords: Asymptotic enumeration, stretched exponential, Airy function, directed acyclic graph, Dyck paths, compacted trees, minimal automata}
}

Search Results

Documents authored by Ghosh Dastidar, Manosij

Asymptotics of Relaxed k-Ary Trees

Abstract

Cite as