论文标题
在单词和排列上连续订购的原子和准阶
Atomicity and well quasi-order for consecutive orderings on words and permutations
论文作者
论文摘要
为两个无限poset中有限的障碍物定义的向下封闭子集的两个顺序理论特性建立了算法可决定性。所考虑的属性是：（a）原子质，即不能作为两个向下封闭的适当子集的联合而分解，或者等效地满足关节嵌入性能； （b）准确排序。这两个posets是：（1）连续子订单下有限字母上的单词； （2）在连续的子透明排序下的有限排列。这四个结果的基础是在有限的有针对性图的路径上的子同心排序的原子性和准级的特征。
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.
