Definability of combinatorial functions and their linear recurrence relations

DOI10.1007/978-3-642-15025-8_21MaRDI QIDQ3586014zbMATH OpenOpenAlexFDO

Authors Tomer Kotek, Johann A. Makowsky

Publication date 3 September 2010

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

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

zbMATH Keywords

combinatoricscounting functionsmonadic second-order logic (MSOL)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

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.

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

Cites work

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

Cited in

(10)

• scientific article; zbMATH DE number 1418435 (Why is no real title available?)
• Application of logic to integer sequences: a survey
• Application of logic to combinatorial sequences and their recurrence relations
• scientific article; zbMATH DE number 3914328 (Why is no real title available?)
• My writing
• Data with logical and statistical constraints
• 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

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)