Algorithms for combinatorial structures: well-founded systems and Newton iterations
From MaRDI portal
Publication:444909
DOI10.1016/J.JCTA.2012.05.007zbMATH Open1246.05012arXiv1109.2688OpenAlexW2098195816MaRDI QIDQ444909FDOQ444909
Michèle Soria, Carine Pivoteau, Bruno Salvy
Publication date: 24 August 2012
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing numerical values. Our framework is an articulation of the constructible classes of Flajolet and Sedgewick with Joyal's species theory. We extend the implicit species theorem to structures of size zero. A quadratic iterative Newton method is shown to solve well-founded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasi-optimal complexity. This iteration transfers to a numerical scheme that converges unconditionally to the values of the generating series inside their disk of convergence. These results provide important subroutines in random generation. Finally, the approach is extended to combinatorial differential systems.
Full work available at URL: https://arxiv.org/abs/1109.2688
Recommendations
Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Explicit solutions, first integrals of ordinary differential equations (34A05)
Cites Work
- Title not available (Why is that?)
- Analytic combinatorics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relax, but don't be too lazy
- Title not available (Why is that?)
- Fast Algorithms for Manipulating Formal Power Series
- Title not available (Why is that?)
- Modern computer algebra
- Une théorie combinatoire des séries formelles
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- A calculus for the random generation of labelled combinatorial structures
- Boltzmann Sampling of Unlabelled Structures
- Une approche combinatoire pour l'itération de Newton-Raphson
- Éclosions combinatoires appliquées à l'inversion multidimensionnelle des séries formelles. (Combinatorial bloomings applied to the multidimensional inversion of formal series)
- Une combinatoire sous-jacente au théorème des fonctions implicites. (Combinatorics underlying the implicit functions theorem)
- On combinatorial differential equations
- On asymmetric structures
- Counting asymmetric enriched trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dérivées directionnelles et développements de Taylor combinatoires. (Directional derivatives and combinatorial Taylor expansions)
Cited In (17)
- Title not available (Why is that?)
- Statistical properties of lambda terms
- A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
- Title not available (Why is that?)
- Counting and generating permutations in regular classes
- Exact-Size Sampling of Enriched Trees in Linear Time
- Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
- Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation
- On the number of planar Eulerian orientations
- On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
- Simplifications of Uniform Expressions Specified by Systems
- Convergence of Newton's method over commutative semirings
- Une approche combinatoire pour l'itération de Newton-Raphson
- Formulae and Asymptotics for Coefficients of Algebraic Functions
- On the number of unary-binary tree-like structures with restrictions on the unary height
- Free integro-differential algebras and Gröbner-Shirshov bases.
- An algorithm computing combinatorial specifications of permutation classes
This page was built for publication: Algorithms for combinatorial structures: well-founded systems and Newton iterations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444909)
