Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations

DOI10.1137/20M1338411MaRDI QIDQ5857006zbMATH OpenOpenAlexFDO

Authors Matthew McDevitt, N. Ruškuc

Publication date 30 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

antichaindigraphjoint embedding propertypath

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Combinatorics of partially ordered sets (06A07) Combinatorics in computer science (68R05)

Abstract: Algorithmic decidability is established for two order-theoretic properties of downward closed subsets defined by finitely many obstructions in two infinite posets. The properties under consideration are: (a) being atomic, i.e. not being decomposable as a union of two downward closed proper subsets, or, equivalently, satisfying the joint embedding property; and (b) being well quasi-ordered. The two posets are: (1) words over a finite alphabet under the consecutive subword ordering; and (2) finite permutations under the consecutive subpermutation ordering. Underpinning the four results are characterisations of atomicity and well quasi-order for the subpath ordering on paths of a finite directed graph.

Recommendations

• On quasi orders of words and the confluence property
• Well quasi-orders generated by a word-shuffle rewriting
• scientific article; zbMATH DE number 758015
• On well-quasi-ordering finite sequences
• Labelled well-quasi-order for permutation classes
• Well quasi ordering finite posets and formal languages
• Schützenberger and Eilenberg theorems for words on linear orderings
• Developments in Language Theory
• scientific article; zbMATH DE number 475611

Cites work

• A survey of consecutive patterns in permutations
• Forbidden substructures and combinatorial dichotomies: WQO and universality
• Graph minors. XX: Wagner's conjecture
• Homogeneous 3-dimensional permutation structures
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• On uniquely k-determined permutations
• Ordering by Divisibility in Abstract Algebras
• Permutation classes
• Ramsey-type and amalgamation-type properties of permutations
• Well quasi-order in combinatorics: embeddings and homomorphisms
• Wilf equivalence relations for consecutive patterns
• WQO is decidable for factorial languages

Cited in

(6)

• On quasi orders of words and the confluence property
• Deciding atomicity of subword-closed languages
• Atoms and partial orders of infinite languages
• Deciding atomicity of subword-closed languages
• Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings
• Well quasi-order and atomicity for combinatorial structures under consecutive orders

This page was built for publication: Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations

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