Simple permutations: Decidability and unavoidable substructures

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

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

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 permutationpermutation classsimple permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Decidability of theories and sets of sentences (03B25)

Related Items (14)

An exact characterization of saturation for permutation matrices ⋮ The enumeration of permutations avoiding 3124 and 4312 ⋮ Labelled well-quasi-order for permutation classes ⋮ Decomposing simple permutations, with enumerative consequences ⋮ Scaling limits of permutation classes with a finite specification: a dichotomy ⋮ WQO is decidable for factorial languages ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ Characterising inflations of monotone grid classes of permutations ⋮ Substitution-closed pattern classes ⋮ Simple permutations and algebraic generating functions ⋮ Universal limits of substitution-closed permutation classes ⋮ Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs ⋮ An algorithm computing combinatorial specifications of permutation classes ⋮ An algorithm for deciding the finiteness of the number of simple permutations in permutation classes

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

This page was built for publication: Simple permutations: Decidability and unavoidable substructures