We show that the set of finite posets is a well-quasi-ordering with respect to a certain relation less than or equal to, called the chain minor relation. To prove this we introduce a similar relation on finite formal languages which also has this property. As a consequence we get that every property which is hereditary with respect to less than or equal to has a test in O(P(c)), whereas c depends on the property. This test has an easy parallelization with the same costs. On a parallel machine (CRCW PRAM) it may be implemented in such a way that it runs in constant time and needs O(P(c))processors. (C) 1995 Academic Press, Inc. [References: 9]
展开▼
机译：我们表明，相对于小于或等于“链次要关系”的某个关系，有限姿态集是一个准序。为了证明这一点，我们在有限形式语言中引入了类似的关系，它也具有此特性。结果，我们得到的每个关于遗传的小于或等于的属性在O（ P （c））中都有一个检验，而c取决于该属性。此测试具有相同成本的简单并行化。在并行机（CRCW PRAM）上，它可以以恒定的时间运行并且需要O（ P （c））个处理器来实现。 （C）1995 Academic Press，Inc. [参考：9]
展开▼
