Atomicity and well quasi-order for consecutive orderings on words and permutations

2020/03/24 by Matthew McDevitt, Nik Ruskuc, Nik Ruškuc +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Algebra and Logic #DNA and Biological Computing #math.CO #msc:05A05 #msc:05C20 #msc:06A07 #msc:68R05 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2003.10743

arxiv created 2020/12/22 · arxiv updated 2020/12/23

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.

Cited by

• Well quasi-order and atomicity for combinatorial structures under consecutive orders

Related

• Well quasi-order and atomicity for combinatorial structures under consecutive orders
• Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings
• Well quasi-orders and the shuffle closure of finite sets
• Dichotomy for orderings?
• Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique