Finding regular insertion encodings for permutation classes

DOI10.1016/J.JSC.2011.11.002zbMATH Open1237.05014arXiv0911.2683OpenAlexW1978066277MaRDI QIDQ765858FDOQ765858

Authors: Vincent Vatter 

Publication date: 22 March 2012

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

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.

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

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

zbMATH Keywords

regular languagepermutation classinsertion encodingrational generating function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• On the effective and automatic enumeration of polynomial permutation classes
• Title not available (Why is that?)
• Refining enumeration schemes to count according to permutation statistics
• Automatic discovery of structural rules of permutation classes
• Sorting via shuffles with a cut after the longest increasing prefix
• Algorithmic coincidence classification of mesh patterns
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• Exhaustive generation for permutations avoiding (colored) regular sets of patterns
• On the centrosymmetric permutations in a class
• InsEnc
• The insertion encoding of permutations
• Permutation patterns and cell decompositions
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Title not available (Why is that?)

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)