{
  "id": "2007.07802",
  "version": "v1",
  "published": "2020-07-15T16:23:31.000Z",
  "updated": "2020-07-15T16:23:31.000Z",
  "title": "Permutree sorting",
  "authors": [
    "Vincent Pilaud",
    "Viviane Pons",
    "Daniel Tamayo Jiménez"
  ],
  "comment": "18 pages, 5 figures",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "Generalizing stack sorting and $c$-sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of $\\{2, \\dots, n-1\\}$, the $(U,D)$-permutree sorting tries to sort the permutation $\\pi \\in \\mathfrak{S}_n$ and fails if and only if there are $1 \\le i < j < k \\le n$ such that $\\pi$ contains the subword $jki$ if $j \\in U$ and $kij$ if $j \\in D$. This algorithm is seen as a way to explore an automaton which either rejects all reduced expressions of $\\pi$, or accepts those reduced expressions for $\\pi$ whose prefixes are all $(U,D)$-permutree sortable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-15T16:23:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68P10",
      "68Q45",
      "68R05",
      "05E99"
    ],
    "keywords": [
      "reduced expressions",
      "permutree sorting algorithm",
      "disjoint subsets",
      "permutree sorting tries",
      "permutation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}