WELL QUASI ORDERING FINITE POSETS AND FORMAL LANGUAGES

We show that the set of finite posets is a well-quasi-ordering with re spect to a certain relation less than or equal to, called the chain mi nor 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. T his test has an easy parallelization with the same costs. On a paralle l 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 Pre ss, Inc.