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

Matthew McDevitt, Nik Ruskuc*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
2 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)495–520
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number1
Early online date23 Mar 2021
DOIs
Publication statusPublished - 2021

Keywords

  • Antichain
  • Digraph
  • Path
  • Joint embedding property

Fingerprint

Dive into the research topics of 'Atomicity and well quasi-order for consecutive orderings on words and permutations'. Together they form a unique fingerprint.

Cite this