{
  "id": "2308.04201",
  "version": "v1",
  "published": "2023-08-08T12:03:11.000Z",
  "updated": "2023-08-08T12:03:11.000Z",
  "title": "Decidability in geometric grid classes of permutations",
  "authors": [
    "Samuel Braunfeld"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO",
    "math.LO"
  ],
  "abstract": "We prove that the basis and the generating function of a geometric grid class of permutations Geom$(M)$ are computable from the matrix $M$, as well as some variations on this result. Our main tool is monadic second-order logic on permutations and words.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-08T12:03:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "geometric grid class",
      "decidability",
      "monadic second-order logic",
      "permutations geom",
      "main tool"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}