An algorithm computing combinatorial specifications of permutation classes
From MaRDI portal
Abstract: This article presents a methodology that automatically derives a combinatorial specification for a permutation class C, given its basis B of excluded patterns and the set of simple permutations in C, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations. The obtained specification yields a system of equations satisfied by the generating function of C, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in C. The method presented is fully algorithmic.
Recommendations
- Combinatorial specification of permutation classes
- Automatic discovery of structural rules of permutation classes
- On the effective and automatic enumeration of polynomial permutation classes
- Combinatorial specifications for juxtapositions of permutation classes
- Finding regular insertion encodings for permutation classes
Cites work
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- A calculus for the random generation of labelled combinatorial structures
- A survey of simple permutations
- Algorithms for combinatorial structures: well-founded systems and Newton iterations
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Analytic combinatorics
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Counting \(\mathbf {(3+1)}\)-avoiding permutations
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial
- Enumerating indices of Schubert varieties defined by inclusions
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Geometric grid classes of permutations
- Inflations of geometric grid classes of permutations
- Large deviations and ratio limit theorems for pattern-avoiding permutations
- Pattern matching for permutations
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Permutation classes
- Simple permutations and algebraic generating functions
- Simple permutations and pattern restricted permutations
- Simple permutations: Decidability and unavoidable substructures
- Structure of random \(312\)-avoiding permutations
- The Brownian limit of separable permutations
- The enumeration of permutations avoiding 2143 and 4231
- The longest common pattern problem for two permutations
- The shape of random pattern-avoiding permutations
Cited in
(11)- On the effective and automatic enumeration of polynomial permutation classes
- A class of recursive permutations which is primitive recursive complete
- Composability of permutation classes
- Automatic discovery of structural rules of permutation classes
- Combinatorial specifications for juxtapositions of permutation classes
- Algorithmic and algebraic aspects of unshuffling permutations
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Exact-Size Sampling of Enriched Trees in Linear Time
- Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
- Scaling limits of permutation classes with a finite specification: a dichotomy
- Combinatorial specification of permutation classes
This page was built for publication: An algorithm computing combinatorial specifications of permutation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526814)
