An algorithm for deciding the finiteness of the number of simple permutations in permutation classes

DOI10.1016/j.aam.2014.12.001zbMath1306.05003arXiv1307.2006OpenAlexW2143220560MaRDI QIDQ2255003

Mathilde Bouvel, Frédérique Bassino, Dominique Rossin, Adeline Pierrot

Publication date: 6 February 2015

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

finite basisautomatonpermutation classsimple permutationpin-permutation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Characterising inflations of monotone grid classes of permutations, Universal limits of substitution-closed permutation classes, Automatic discovery of structural rules of permutation classes, Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs, An algorithm computing combinatorial specifications of permutation classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumeration of pin-permutations
• Decomposing simple permutations, with enumerative consequences
• Simple permutations and algebraic generating functions
• Simple permutations: Decidability and unavoidable substructures
• Simple permutations and pattern restricted permutations
• AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS
• Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
• Efficient string matching
• Combinatorial specification of permutation classes
• Transitiv orientierbare Graphen
• Algorithms and Computation