{
  "id": "0907.5420",
  "version": "v1",
  "published": "2009-07-30T20:12:15.000Z",
  "updated": "2009-07-30T20:12:15.000Z",
  "title": "Definability of Combinatorial Functions and Their Linear Recurrence Relations",
  "authors": [
    "T. Kotek",
    "J. A. Makowsky"
  ],
  "comment": "18 pages, 1 table",
  "journal": "Lecture Notes in Computer Science, vol. 6300, pages 444-462, 2010",
  "categories": [
    "math.CO",
    "math.LO"
  ],
  "abstract": "We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over $\\mathbb Z$ or ${\\mathbb Z}_m$ and allow an interpretation as counting the number of relations satisfying a property expressible in Monadic Second Order Logic (MSOL). C. Blatter and E. Specker (1981) showed that if such a function $f$ counts the number of binary relations satisfying a property expressible in MSOL then $f$ satisfies for every $m \\in \\mathbb{N}$ a linear recurrence relation over $\\mathbb{Z}_m$. In this paper we give a complete characterization in terms of definability in MSOL of the combinatorial functions which satisfy a linear recurrence relation over $\\mathbb{Z}$, and discuss various extensions and limitations of the Specker-Blatter theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-07-30T20:12:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "03C13",
      "68R05",
      "68R15"
    ],
    "keywords": [
      "linear recurrence relation",
      "combinatorial functions",
      "definability",
      "monadic second order logic",
      "natural numbers"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.5420K"
    }
  }
}