{
  "id": "2404.08415",
  "version": "v1",
  "published": "2024-04-12T12:01:59.000Z",
  "updated": "2024-04-12T12:01:59.000Z",
  "title": "Asymptotics of relaxed $k$-ary trees",
  "authors": [
    "Manosij Ghosh Dastidar",
    "Michael Wallner"
  ],
  "comment": "12 pages, 3 figures, 3 tables",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-04-12T12:01:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "05A16",
      "05C20",
      "05C05"
    ],
    "keywords": [
      "ary tree",
      "asymptotic",
      "arbitrary finite arity",
      "minimal deterministic finite automata accepting",
      "ordered directed acyclic graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}