Finding regular insertion encodings for permutation classes

DOI10.1016/J.JSC.2011.11.002MaRDI QIDQ765858zbMATH OpenOpenAlexFDO

Authors Vincent Vatter

Publication date 22 March 2012

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

insertion encodingpermutation classrational generating functionregular language

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16)

Abstract: We describe a practical algorithm which computes the accepting automaton for the insertion encoding of a permutation class, whenever this insertion encoding is regular. This algorithm is implemented in the accompanying Maple package INSENC, which can automatically compute the rational generating functions for such classes.

Recommendations

• The insertion encoding of permutations
• Computing permutation encodings
• Rationality for subclasses of 321-avoiding permutations
• Automatic discovery of structural rules of permutation classes
• Counting and generating permutations in regular classes

Cites work

• Analytic combinatorics
• Finite transition matrices for permutations avoiding pairs of length four patterns
• Finitely labeled generating trees and restricted permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Linear Automaton Transformations
• On growth rates of closed permutation classes
• Partially well-ordered closed sets of permutations
• Permutation classes of polynomial growth
• Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi
• The insertion encoding of permutations
• The number of Baxter permutations
• Wilf classes of pairs of permutations of length 4

Cited in

(20)

• Computing permutation encodings
• InsEnc
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Exhaustive generation for permutations avoiding (colored) regular sets of patterns
• Permutation patterns and cell decompositions
• The insertion encoding of permutations
• Regular languages of plus- and minus-(in)decomposable permutations
• Refining enumeration schemes to count according to permutation statistics
• Automatic discovery of structural rules of permutation classes
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• On the centrosymmetric permutations in a class
• An algorithm computing combinatorial specifications of permutation classes
• On the effective and automatic enumeration of polynomial permutation classes
• Algorithmic coincidence classification of mesh patterns
• Sorting via shuffles with a cut after the longest increasing prefix
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• Combinatorial exploration: an algorithmic framework for enumeration
• Sorting permutations using a pop stack with a bypass
• Pop stacks with a bypass

Describes a project that uses

Uses Software

• Maple

This page was built for publication: Finding regular insertion encodings for permutation classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765858)