{
  "id": "1305.0640",
  "version": "v1",
  "published": "2013-05-03T08:42:01.000Z",
  "updated": "2013-05-03T08:42:01.000Z",
  "title": "Enumeration of generalized $BCI$ lambda-terms",
  "authors": [
    "Olivier Bodini",
    "Danièle Gardy",
    "Bernhard Gittenberger",
    "Alice Jacquot"
  ],
  "comment": "17 pages, 5 figures",
  "categories": [
    "math.CO",
    "math.LO"
  ],
  "abstract": "We investigate the asymptotic number of elements of size $n$ in a particular class of closed lambda-terms (so-called $BCI(p)$-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of $BCK(p)$-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lowerestimates for the number of closed lambda-terms of size $n$. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. $BCK(p)$-terms are discussed briefly.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-05-03T08:42:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "03B40"
    ],
    "keywords": [
      "counting sequence",
      "closed lambda-terms",
      "enumeration",
      "recurrence relation",
      "generating function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1305.0640B"
    }
  }
}