Definability of Combinatorial Functions and Their Linear Recurrence Relations

DOI10.1007/978-3-642-15025-8_21zbMath1287.05008arXiv0907.5420OpenAlexW1564027968MaRDI QIDQ3586014

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)

Related Items

Growth properties of power-free languages

Cites Work

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