Definability of combinatorial functions and their linear recurrence relations

DOI10.1007/978-3-642-15025-8_21zbMATH Open1287.05008arXiv0907.5420OpenAlexW1564027968MaRDI QIDQ3586014FDOQ3586014

Authors: Tomer Kotek, Johann A. Makowsky 

Publication date: 3 September 2010

Published in: Fields of Logic and Computation (Search for Journal in Brave)

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 $mathbbZ$ or ${mathbbZ}_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 $minmathbbN$ 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 $mathbbZ$, and discuss various extensions and limitations of the Specker-Blatter theorem.

Full work available at URL: https://arxiv.org/abs/0907.5420

Recommendations

• The Specker-Blatter theorem revisited
• scientific article; zbMATH DE number 3914328
• The Specker-Blatter theorem does not hold for quaternary relations
• Logical definability of counting functions
• Application of logic to integer sequences: a survey

zbMATH Keywords

combinatoricscounting functionsmonadic second-order logic (MSOL)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Title not available (Why is that?)
• Elements of finite model theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Weak Second‐Order Arithmetic and Finite Automata
• The Polynomial of Mittag-Leffler
• The speed of hereditary properties of graphs
• Practical Extrapolation Methods
• Excluding Induced Subgraphs III: A General Asymptotic
• Growth constants of minor-closed classes of graphs
• On the size of hereditary classes of graphs
• The penultimate rate of growth for graph properties
• The Specker-Blatter theorem does not hold for quaternary relations
• The Specker-Blatter theorem revisited
• Positive rational sequences
• Title not available (Why is that?)
• Measures on monotone properties of graphs
• A technology for reverse-engineering a combinatorial problem from a rational generating function

Cited In (7)

• Application of logic to integer sequences: a survey
• Title not available (Why is that?)
• Growth properties of power-free languages
• The Specker-Blatter theorem does not hold for quaternary relations
• The Specker-Blatter theorem revisited
• Recursively defined combinatorial functions: Extending Galton's board
• Title not available (Why is that?)

This page was built for publication: Definability of combinatorial functions and their linear recurrence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586014)