{
  "id": "1803.07234",
  "version": "v1",
  "published": "2018-03-20T03:18:12.000Z",
  "updated": "2018-03-20T03:18:12.000Z",
  "title": "Remarks on formal languages and the model theory of monoids",
  "authors": [
    "Christopher D. C. Hawthorne"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "Given a monoid $(M,\\cdot ,\\epsilon )$ that is freely generated on a finite set $\\Sigma $, it is shown that the quantifier-free definable subsets of $M$ form a proper subclass of the star-free languages over $\\Sigma $. Furthermore, a subset $A\\subseteq M$ is shown to be a regular language over $\\Sigma $ if and only if the $\\phi $-rank of $x=x$ is zero, where $\\phi (x; v)$ is the formula $xv\\in A$. This latter result is extended to arbitrary monoids with recognizable subsets replacing regular languages.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-20T03:18:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C65",
      "68Q45",
      "68Q70",
      "F.4.1",
      "F.4.3"
    ],
    "keywords": [
      "formal languages",
      "model theory",
      "recognizable subsets replacing regular languages",
      "star-free languages",
      "proper subclass"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}