Simple permutations: Decidability and unavoidable substructures

DOI10.1016/j.tcs.2007.10.037zbMath1133.05001arXivmath/0609211MaRDI QIDQ2474234

Robert Brignall, Vincent R. Vatter, Nikola Ruškuc

Publication date: 5 March 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

restricted permutation; permutation class; simple permutation

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

03B25: Decidability of theories and sets of sentences

Related Items

Boundary properties of well-quasi-ordered sets of graphs, An algorithm computing combinatorial specifications of permutation classes, Substitution-closed pattern classes, Characterising inflations of monotone grid classes of permutations, An algorithm for deciding the finiteness of the number of simple permutations in permutation classes, The enumeration of permutations avoiding 3124 and 4312, Decomposing simple permutations, with enumerative consequences, WQO is decidable for factorial languages, Simple permutations and algebraic generating functions

Cites Work

• Unnamed Item
• Unnamed Item
• Partially well-ordered closed sets of permutations
• Criterion for smoothness of Schubert varieties in Sl(n)/B
• A survey of stack-sorting disciplines
• Regular closed sets of permutations.
• Minimal antichains in well-founded quasi-orders with an application to tournaments
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Decomposing simple permutations, with enumerative consequences
• Simple permutations and algebraic generating functions
• Simple permutations and pattern restricted permutations
• The insertion encoding of permutations
• On Intervals in Relational Structures
• Graph Classes: A Survey
• Ordering by Divisibility in Abstract Algebras
• Restricted permutations