Well quasi ordering finite posets and formal languages (Q1898732)

We show that the set of finite posets is a well-quasi-ordering with respect to a certain relation \(\preceq\), called 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 \(\preceq\) 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 \(\text{(CRCW} \backslash \text{PRAM)}\) it may be implemented in such a way that it runs in constant time and needs \(O (|P |^c)\) processors.