Algorithms for combinatorial structures: well-founded systems and Newton iterations
From MaRDI portal
(Redirected from Publication:444909)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4143982 (Why is no real title available?)
- scientific article; zbMATH DE number 3983158 (Why is no real title available?)
- scientific article; zbMATH DE number 3989612 (Why is no real title available?)
- scientific article; zbMATH DE number 4025850 (Why is no real title available?)
- scientific article; zbMATH DE number 125879 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1111371 (Why is no real title available?)
- A calculus for the random generation of labelled combinatorial structures
- Analytic combinatorics
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann oracle for combinatorial systems
- Boltzmann sampling of unlabelled structures
- Counting asymmetric enriched trees
- Dérivées directionnelles et développements de Taylor combinatoires. (Directional derivatives and combinatorial Taylor expansions)
- Fast Algorithms for Manipulating Formal Power Series
- Fast computation of power series solutions of systems of differential equations
- Modern computer algebra
- On asymmetric structures
- On combinatorial differential equations
- Relax, but don't be too lazy
- Une approche combinatoire pour l'itération de Newton-Raphson
- Une combinatoire sous-jacente au théorème des fonctions implicites. (Combinatorics underlying the implicit functions theorem)
- Une théorie combinatoire des séries formelles
- Éclosions combinatoires appliquées à l'inversion multidimensionnelle des séries formelles. (Combinatorial bloomings applied to the multidimensional inversion of formal series)
Cited in
(17)- Formulae and asymptotics for coefficients of algebraic functions
- Statistical properties of lambda terms
- scientific article; zbMATH DE number 6928782 (Why is no real title available?)
- Recursive combinatorial structures: enumeration, probabilistic analysis and random generation
- A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
- scientific article; zbMATH DE number 5139236 (Why is no real title available?)
- 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
- On the number of planar Eulerian orientations
- On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
- Convergence of Newton's method over commutative semirings
- Une approche combinatoire pour l'itération de Newton-Raphson
- Simplifications of Uniform Expressions Specified by Systems
- 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)
